1499. The maximum pile.then/deque

1499. The maximum value that satisfies the inequality

You are given an array points and an integer k .Each element in the array represents the coordinates of a point on a two-dimensional plane, and is sorted according to the value of the abscissa x from small to large.That is, points[i] = [xi, yi], and under the premise of 1 <= i < j <= points.length, xi is always established.

Please find the maximum value of yi + yj + |xi - xj|, where |xi - xj|<= k and 1 <= i < j <= points.length.

The item test data guarantees that there are at least one pair of points that satisfy |xi - xj| <= k.

Example 1:

Input:points = [[1,3],[2,0],[5,10],[6,-10]], k = 1Output:4Explanation: The first two points satisfy |xi - xj| <= 1 , substituting into the equation for calculation, the value 3 + 0 + |1 - 2| = 4 is obtained.The third and fourth points also satisfy the condition, resulting in the value 10 + -10 + |5 - 6| = 1 .There are no other points that satisfy the condition, so the largest of 4 and 1 is returned.

Example 2:

Input:points = [[0,0],[3,0],[9,2]], k = 3Output:3Explanation: Only the first two points satisfy |xi - xj| <= 3 , and after substituting into the equation, the value 0 + 0 + |0 - 3| = 3 is obtained.

Tip:

• 2 <= points.length <= 10^5
• points[i].length == 2
• -10^8 <= points[i][0], points[i][1] <= 10^8
• 0 <= k <= 2 * 10^8
• For all 1 <= i < j <= points.length, points[i][0] < points[j][0] holds.That is, xi is strictly increasing.

Source: LeetCode
Link: https://leetcode.cn/problems/max-value-of-equation
The copyright belongs to LeetCode.For commercial reprints, please contact the official authorization, and for non-commercial reprints, please indicate the source.

Results of the questions

Success, heap, later reference tag monotonic queue

Method 1: Heap

yi + yj + |xi - xj|, because xi

The main feature is that it adopts the lazy deletion strategy, saves the position of the previous index and yi-xi, and sorts the heap according to yi-xi from large to small

1. Delete the distance between the top of the heap and x (lazy deletion)

2. Non-empty comparison max(yi+yj+heap top, ans)

3. The current element {xi,yi-xi} is added to the heap

class Solution {public int findMaxValueOfEquation(int[][] points, int k) {PriorityQueue 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;}}

Time complexity: O(nlogn)

Space complexity: O(n)

Method 2: Deque (Monotone Queue)

1. Consider two situations:

- the new value is smaller than the old value, may the new value be counted as a valid value in the answer?possible.The previous old value is dequeued, and the new value may become the maximum

- the new value is greater than the old value, can the old value be included as a valid value in the answer?impossible.The old value is dequeued before, and the new value has not been dequeued, so the old value is invalid.

2. To sum up, this question can maintain a monotonic decline.The maximum value is first, and the minimum value is last.The previous value is dequeued if the distance is exceeded, and the latter value is smaller than the new value, dequeued, and then the new value is added to the end of the queue.In this way, the complexity of O(n) is used to maintain the same maximum value as the heap.

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;}}

Time complexity: O(n)

Space complexity: O(n)