LeetCode题解:数组的最大美丽值

简介: LeetCode题解:数组的最大美丽值

好久没打力扣周赛了,今天做了下,以前都是可以肝三个题的,今天第二题就卡住了😭😭😭

下面我就浅浅分析下这个题吧,我一定能给你讲明白的😀😀😀

我们先来康康题目的意思啦,为了方便观看,我直接到力扣那里截了个屏过来✅

划重点

这道题免费哟,直接上链接🥰🥰🥰数组的最大美丽值

题目都看完了吧?

我们现在来聊聊这道题的思路

思路

这道题如果采用常规的暴力法去做的话,是肯定的会TLE(超时)的,别问怎么知道的,因为尝试过了😤😤😤,其实看看这数据范围也知道,暴力法会超时~

那我们可以怎么优化呢,且听我徐徐道来

重点:我们对数组从小到大排序一下(这个其实并不会影响我们找题目中说的美丽值,因为需要找的是相同元素的子序列的长度嘛,所以即使排序了肯定也没影响啦)

😀好滴,排序完了后,我们开始浅浅分析一波

因为数组中任何的一个数x,可以是x-k 到 x+k 区间中的数,我们的目标是在数组中能够通过改变元素的值从而获得更多相等的数

因为在[x-k,x+k]区间的数都可以变成x,那么,我们可以得出一个结论,若数组中任何一个元素和最小的那个元素的差值都<=2*k的话,那么这个数组中的每个元素都能改变成x

相信你一定看懂了吧,没看懂可以在回味一下

好了,我们接下来就开始coding

时间复杂度:nlogn

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        //获取长度
        int len = nums.size();
        //排序,方便处理
        sort(nums.begin(),nums.end());
        // r是右指针,ans记录最终的答案
        int r=0,ans=0;
        for(int i=0;i<len;i++){
            //这里 nums[r]-nums[i] <= 2*k 就是题解中说的,数组中任何一个元素和最小的那个元素的差值都<=2*k
            //nums[i] 一定是[i,r]区间中最小的,因为排序了的,所以这就是为什么要排序的原因
            while(r<len&&nums[r]-nums[i]<=2*k){
                r++;
            }
            // r-i 就表示数组中 [r,i]这个区间的数都能变成相等的,我们这里是需要求长度,所以直接r-i
            // 在所有区间中,取最大的那个长度
            ans=max(ans,r-i);
        }
        return ans;
    }
};

OKOK,题解完毕,这道题算是比较经典了,结合注释相信大家都看懂了吧,看懂了的掌声响起来😋,若还有不懂的地方,也是可以录制视频来讲解的额(掌声响起来😍)


相关文章
|
2月前
|
算法
Leetcode 初级算法 --- 数组篇
Leetcode 初级算法 --- 数组篇
40 0
|
4月前
|
算法
LeetCode第53题最大子数组和
LeetCode第53题"最大子数组和"的解题方法,利用动态规划思想,通过一次遍历数组,维护到当前元素为止的最大子数组和,有效避免了复杂度更高的暴力解法。
LeetCode第53题最大子数组和
|
4月前
|
存储 Java API
LeetCode------合并两个有序数组(4)【数组】
这篇文章介绍了LeetCode上的"合并两个有序数组"问题,并提供了三种解法:第一种是使用Java的Arrays.sort()方法直接对合并后的数组进行排序;第二种是使用辅助数组和双指针技术进行合并;第三种则是从后向前的双指针方法,避免了使用额外的辅助数组。
LeetCode------合并两个有序数组(4)【数组】
|
4月前
|
搜索推荐 索引 Python
【Leetcode刷题Python】牛客. 数组中未出现的最小正整数
本文介绍了牛客网题目"数组中未出现的最小正整数"的解法,提供了一种满足O(n)时间复杂度和O(1)空间复杂度要求的原地排序算法,并给出了Python实现代码。
120 2
|
4月前
|
Python
【Leetcode刷题Python】剑指 Offer 03. 数组中重复的数字
解决剑指Offer题目 "数组中重复的数字" 的Python实现方法,通过使用字典来记录数组中每个数字的出现次数,快速找出重复的数字。
39 1
LeetCode------找到所有数组中消失的数字(6)【数组】
这篇文章介绍了LeetCode上的"找到所有数组中消失的数字"问题,提供了一种解法,通过两次遍历来找出所有未在数组中出现的数字:第一次遍历将数组中的每个数字对应位置的值增加数组长度,第二次遍历找出所有未被增加的数字,即缺失的数字。
|
4月前
|
前端开发
LeetCode------移动零(5)【数组】
这篇文章介绍了LeetCode上的"移动零"问题,提出了一种使用双指针的原地操作解法,该方法首先将非零元素移动到数组前端并保持相对顺序,然后填充后续位置为零,以达到题目要求。
|
2月前
【LeetCode-每日一题】 删除排序数组中的重复项
【LeetCode-每日一题】 删除排序数组中的重复项
21 4
|
2月前
|
索引
Leetcode第三十三题(搜索旋转排序数组)
这篇文章介绍了解决LeetCode第33题“搜索旋转排序数组”的方法,该问题要求在旋转过的升序数组中找到给定目标值的索引,如果存在则返回索引,否则返回-1,文章提供了一个时间复杂度为O(logn)的二分搜索算法实现。
19 0
Leetcode第三十三题(搜索旋转排序数组)
|
2月前
|
算法 C++
Leetcode第53题(最大子数组和)
这篇文章介绍了LeetCode第53题“最大子数组和”的动态规划解法,提供了详细的状态转移方程和C++代码实现,并讨论了其他算法如贪心、分治、改进动态规划和分块累计法。
68 0