【Leetcode Daily】2779数组的最大美丽值

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个整数数组和一个数字 k，让你对每一个位的数字可以做一个操作也就是上下浮动不超过 k 的数值，最后整个数组最多的数字的数量就是要求的结果。

思路分享

• 陆爻齐吃亏在了审题不当，题目中的子序列是可以删除数组的内容，也就是说，顺序不重要，只要找到最多的公共数值就行。

• 而要找到这个公共数值，可以这么做，先排序，然后开始不定长滑动窗口（【Leetcode Daily】3090每个字符最多出现两次的最长字符串），而不满足窗口的条件是，左窗口加上 k 的值小于右窗口减去 k 的值，这意味着窗口的左右两侧不再有公共的数值。

• 数组经过排序，所以只要左窗口不断向右滑动，总会再次处于左右窗口有公共数值的阶段。这样一来窗口就会高效率地遍历并找到有公共值的最长子序列。

  https://leetcode.cn/problems/maximum-beauty-of-an-array-after-applying-operation/solutions/2345805/pai-xu-shuang-zhi-zhen-by-endlesscheng-hbqx/

代码解答（强烈建议自行解答后再看）

• 参考题解

class Solution {
public:
    int maximumBeauty(vector<int>& nums, int k) {
        int ans = 1;
        int left = 0;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size(); i++) {
            while (nums[i]-k > nums[left]+k) {
                left++;
            }
            ans = max(ans, i-left+1);
        }
        return ans;
    }
};