Leetcode 2779. Maximum Beauty of an Array After Applying Operation

[Woodyiiiiiii]

2779. Maximum Beauty of an Array After Applying Operation

2779. Maximum Beauty of an Array After Applying Operation

这道题很有意思，考验思维，花费了我一些时间，但其中的逻辑思维很有意义。

首先看完题目，再看数据范围，数组长度n最大为10^5，元素大小10^5，k最大为10^5。所以最多要二分/排序/堆。更重要的是，要对k和n其中一个值简化，也就是不能直接遍历。

接着继续挖掘题目信息，求的是最长子序列，涉及到范围变化，所以可以排序，能方便很多。

然后，从n、每个nums[i]和k出发，思考如何求解。因为排序，题目求的可以转化为每个数据最多操作一次后数值相等的最大连续子区间。那按照贪心的思想，每个数都尽可能往中间数值靠。当然这个最终的中间值不一定是数组中出现的(这也是我吃了一个WA的原因)。

再发现，我们现在求的是最大的子区间，其中这个区间每个数都可以在操作后满足相等，结合要省略k/n，一次遍历n这些条件，那么就自然想到滑动窗口了。所以以后固定范围可以考虑滑动窗口。

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        Arrays.sort(nums);
        int n = nums.length;
        if (n == 1) {
            return 1;
        }
        if (nums[0] + k >= nums[n - 1] - k) {
            return n;
        }
        int ans = 1;

        int l = 0, r = 0;
        while (r < n) {
            while (l < r && nums[r] - k > nums[l] + k) {
                l++;
            }
            ans = Math.max(ans, r - l + 1);
            r++;
        }

        return ans;
    }
}

总结：

1. 理解题意/注意数据范围
2. 思考题目性质/利用算法，逻辑思维
3. 求解/写代码

当然这道题还有另一种做法——差分。

这道题是跟范围有关，对于某个数，他的操作范围能直接得到，相当于在某个范围同时+1，表示当前范围达到的元素个数。然后，这个范围最大值肯定是数组最大值，不能再超过了。然后就可以得到以下代码：

func maximumBeauty(nums []int, k int) int {
    n := len(nums)
    mx := 0
    for i := 0; i < n; i++ {
        mx = max(mx, nums[i])
    }
    d := make([]int, mx + 1)
    for i := 0; i < n; i++ {
        d[max(nums[i] - k, 0)] ++
        if nums[i] + k + 1 <= mx {
            d[nums[i] + k + 1] --
        }
    }
    cur,ans := 0,0 
    for i := 0; i <= mx; i++ {
        cur += d[i]
        ans = max(ans, cur)
    }
    return ans
}

func max(a, b int) int {
    if a > b {
        return a
    }
    return b
}

时间范围是O(n)，不用排序。

缺点是这道题跟值域有关，如果元素范围是10^9，就不行了。