Given an array points containing the coordinates of points on a 2D plane, sorted by the x-values, where points[i] = [xi, yi] such that xi < xj for all 1 <= i < j <= points.length. You are also given an integer k.
Find the maximum value of the equation yi + yj + |xi - xj| where |xi - xj| <= k and 1 <= i < j <= points.length. It is guaranteed that there exists at least one pair of points that satisfy the constraint |xi - xj| <= k.
Example 1:
Input: points = [[1,3],[2,0],[5,10],[6,-10]], k = 1 Output: 4 Explanation: The first two points satisfy the condition |xi - xj| <= 1 and if we calculate the equation we get 3 + 0 + |1 - 2| = 4. Third and fourth points also satisfy the condition and give a value of 10 + -10 + |5 - 6| = 1. No other pairs satisfy the condition, so we return the max of 4 and 1.
Example 2:
Input: points = [[0,0],[3,0],[9,2]], k = 3 Output: 3 Explanation: Only the first two points have an absolute difference of 3 or less in the x-values, and give the value of 0 + 0 + |0 - 3| = 3.
Constraints:
2 <= points.length <= 10^5points[i].length == 2-10^8 <= points[i][0], points[i][1] <= 10^80 <= k <= 2 * 10^8points[i][0] < points[j][0]for all1 <= i < j <= points.lengthxiform a strictly increasing sequence.
Observation
Since xj > xi, so |xi – xj| + yi + yj => xj + yj + (yi – xi)
We want to have yi – xi as large as possible while need to make sure xj – xi <= k.
Solution 1: Priority Queue / Heap
Put all the points processed so far onto the heap as (y-x, x) sorted by y-x in descending order.
Each new point (x_j, y_j), find the largest y-x such that x_j – x <= k.
Time complexity: O(nlogn)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua class Solution { public: int findMaxValueOfEquation(vector<vector<int>>& points, int k) { priority_queue<pair<int, int>> q; // {y - x, x} q.emplace(0, -1e9); int ans = INT_MIN; for (const auto& p : points) { const int x = p[0], y = p[1]; while (!q.empty() && x - q.top().second > k) q.pop(); if (!q.empty()) ans = max(ans, x + y + q.top().first); q.emplace(y - x, x); } return ans; } }; |
Solution 2: Monotonic Queue
Maintain a monotonic queue:
1. The queue is sorted by y – x in descending order.
2. Pop then front element when xj – x_front > k, they can’t be used anymore.
3. Record the max of {xj + yj + (y_front – x_front)}
4. Pop the back element when yj – xj > y_back – x_back, they are smaller and lefter. Won’t be useful anymore.
5. Finally, push the j-th element onto the queue.
Time complexity: O(n)
Space complexity: O(n)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua class Solution { public: int findMaxValueOfEquation(vector<vector<int>>& points, int k) { deque<pair<int, int>> q; // {y - x, x} Sort by y - x. int ans = INT_MIN; for (const auto& p : points) { const int xj = p[0]; const int yj = p[1]; // Remove invalid points, e.g. xj - xi > k while (!q.empty() && xj - q.front().second > k) q.pop_front(); if (!q.empty()) ans = max(ans, xj + yj + q.front().first); while (!q.empty() && yj - xj >= q.back().first) q.pop_back(); q.emplace_back(yj - xj, xj); } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 |
class Solution { public int findMaxValueOfEquation(int[][] points, int k) { var q = new ArrayDeque<Integer>(); int ans = Integer.MIN_VALUE; for (int i = 0; i < points.length; ++i) { int xj = points[i][0]; int yj = points[i][1]; while (!q.isEmpty() && xj - points[q.getFirst()][0] > k) { q.removeFirst(); } if (!q.isEmpty()) { ans = Math.max(ans, xj + yj + points[q.getFirst()][1] - points[q.getFirst()][0]); } while (!q.isEmpty() && yj - xj >= points[q.getLast()][1] - points[q.getLast()][0]) { q.removeLast(); } q.offer(i); } return ans; } } |
python3
|
1 2 3 4 5 6 7 8 9 10 11 |
# Author: Huahua class Solution: def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int: ans = float('-inf') q = deque() # {(y - x, x)} for x, y in points: while q and x - q[0][1] > k: q.popleft() if q: ans = max(ans, x + y + q[0][0]) while q and y - x >= q[-1][0]: q.pop() q.append((y - x, x)) return ans |
请尊重作者的劳动成果，转载请注明出处！花花保留对文章／视频的所有权利。
如果您喜欢这篇文章／视频，欢迎您捐赠花花。
If you like my articles / videos, donations are welcome.
huahualeetcode
Be First to Comment