1499. 满足不等式的最大值 堆/双端队列

1499. 满足不等式的最大值

给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标，并按照横坐标 x 的值从小到大排序。也就是说 points[i] = [xi, yi] ，并且在 1 <= i < j <= points.length 的前提下， xi < xj 总成立。

请你找出 yi + yj + |xi - xj| 的 最大值，其中 |xi - xj| <= k 且 1 <= i < j <= points.length。

题目测试数据保证至少存在一对能够满足 |xi - xj| <= k 的点。

示例 1：

输入：points = [[1,3],[2,0],[5,10],[6,-10]], k = 1
输出：4
解释：前两个点满足 |xi - xj| <= 1 ，代入方程计算，则得到值 3 + 0 + |1 - 2| = 4 。第三个和第四个点也满足条件，得到值 10 + -10 + |5 - 6| = 1 。
没有其他满足条件的点，所以返回 4 和 1 中最大的那个。

示例 2：

输入：points = [[0,0],[3,0],[9,2]], k = 3
输出：3
解释：只有前两个点满足 |xi - xj| <= 3 ，代入方程后得到值 0 + 0 + |0 - 3| = 3 。

提示：

• 2 <= points.length <= 10^5
• points[i].length == 2
• -10^8 <= points[i][0], points[i][1] <= 10^8
• 0 <= k <= 2 * 10^8
• 对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/max-value-of-equation
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

成功，堆，后面参考标签单调队列

 方法1：堆

yi + yj + |xi - xj|，因为xi<xj，所以这个式子和变为 yi+yj+(xj-xi)=(xj+yj)+(yi-xi)

主要特点是采取了懒删除策略,保存前面索引的位置与 yi-xi,按 yi-xi从大到小排序堆

1. 把堆顶和x距离太远的删掉（懒删除）

2. 非空情况比较 max(yi+yj+堆顶,ans)

3. 当前元素 {xi,yi-xi} 加入堆

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        PriorityQueue<int[]> pq=  new PriorityQueue<>((a,b)->b[1]-a[1]);
        int n = points.length;
        int ans = Integer.MIN_VALUE;
        for(int i = 0; i < n; i++){
            int[] point = points[i];
            while (!pq.isEmpty()&&point[0]-pq.peek()[0]>k) pq.poll();
            if(!pq.isEmpty()) ans = Math.max(ans,point[0]+point[1]+pq.peek()[1]);
            pq.offer(new int[]{point[0],point[1]-point[0]});
        }
        return ans;
    }
}

时间复杂度：O(nlogn)

空间复杂度：O(n)

方法2：双端队列（单调队列）

1. 考虑两个情况：

        - 新的值比旧的值小，新的值可能作为有效值算到答案中吗？可能。前面旧值出队，新的值可能变成最大

        - 新的值比旧的值大，旧的值可能作为有效值到答案中吗？不可能。前面旧值出队，新的值还没出队，所以旧值无效了。

2. 综上，本题维护一个单调下降即可。最大值在最前，最小值最后。前面的值距离超出就出队，后面的值比新值小的就出队，然后新的值加在队列的末尾。这样就用O(n) 的复杂度维护了和堆一样拿到最大值得效果。

class Solution {
    public int findMaxValueOfEquation(int[][] points, int k) {
        int n = points.length;
        int[] deque = new int[n];
        int start = 0;
        int end = 0;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int[] point = points[i];
            while (end!=start && point[0] - points[deque[start]][0] > k) ++start;
            if (end!=start) ans = Math.max(ans, point[0] + point[1] + (points[deque[start]][1]-points[deque[start]][0]));
            int v = point[1] - point[0];
            while (end!=start && points[deque[end-1]][1]-points[deque[end-1]][0] < v)--end;
            deque[end++]=i;
        }
        return ans;
    }
}

时间复杂度：O(n)

空间复杂度：O(n)