6929. 数组的最大美丽值 (opens new window)

1.排序+双指针

破题关键在于理解为什么可以进行排序？

①题目没有要求返回最大美丽值对应子序列操作之前的子序列。②子序列不要求相邻。③子序列只要求元素值相等，没有递增之类的其它要求。

子序列问题要留意是否可以进行排序，思考过程如下：

• 排序前最优结果A，经过排序过后得到的有序数组还能否将A搜索出来？
• 有序序列得到的最优结果A，在排序前的原数组能否搜索出来？

显然本题满足上面两个条件，只要一个子序列经过操作后能够变为相等序列，那么原子序列的最小值和最大值之差一定在2*k范围之内。排序过后的原数组可以直接使用双指针来实现子序列的最大区间和的计算。

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int res=1;
        Arrays.sort(nums);
        int left=0;
        for(int i=0;i<nums.length;i++){
            if(nums[i]-nums[left]>2*k){
                while(left<i&&nums[i]-nums[left]>2*k){
                    res=Math.max(res,i-left);
                    left++;
                }
            }
        }
        res=Math.max(res,nums.length-left);
        return res;
    }
}

2.差分数组

题目等价于计算最大重叠区间个数。

如上图所示，想象这是在一个数轴上，同色方块表示每个元素nums[i]能够表示的区间范围为【nums[i]-k,nums[i]+k】，每一个元素的区间都落在数轴上，对应能表示的区间高度加1。重叠最高的区间的高度即对应最大的美丽值。

• 数组大小

记nums数组最小值最大值分别为min和max，那么数轴上能够表示的区间范围就在【min-k,max+k】，因此需要开辟数组空间大小为max-min+2*k+2。并设置偏置。

• 使用差分数组在O(n)时间复杂度内维护区间高度数组

具体来说，对于元素num[i]，在差分数组索引位置num[i]-k加1，结尾索引位置num[i]+k减1，从而终止当前这个区间的传播(如果不为零说明这个位置在其它区间上有传播)。

class Solution {
    public int maximumBeauty(int[] nums, int k) {
        int res=1;
        int min=Integer.MAX_VALUE;
        int max=Integer.MIN_VALUE;
        for(int i=0;i<nums.length;i++){
            min=Math.min(min,nums[i]);
            max=Math.max(max,nums[i]);
        }
        int[] a=new int[max-min+2*k+2];
        int base=min-k;
        for(int i=0;i<nums.length;i++){
            int left=nums[i]-k;
            int right=nums[i]+k;
            a[left-base]++;
            a[right-base+1]--;
        }
        for(int i=1;i<a.length;i++){
            a[i]+=a[i-1];
            res=Math.max(res,a[i]);
        }
        return res;
    }
}