class Solution {
public:
int findMaxValueOfEquation(vector<vector<int>>& points, int k) {
}
};
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^5points[i].length == 2-10^8 <= points[i][0], points[i][1] <= 10^80 <= k <= 2 * 10^81 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。原站题解
javascript 解法, 执行用时: 216 ms, 内存消耗: 73.4 MB, 提交时间: 2023-07-21 10:20:17
/**
* @param {number[][]} points
* @param {number} k
* @return {number}
*/
var findMaxValueOfEquation = function (points, k) {
let ans = Number.MIN_SAFE_INTEGER;
let q = Array(points.length); // 用数组模拟双端队列
let left = 0, right = 0; // 实际元素下标在左闭右开区间 [left,right) 内
for (const [x, y] of points) {
while (left < right && q[left][0] < x - k) // 队首超出范围
left++; // 弹它！
if (left < right)
ans = Math.max(ans, x + y + q[left][1]); // 加上最大的 yi-xi
while (left < right && q[right - 1][1] <= y - x) // 队尾不如新来的强
right--; // 弹它！
q[right++] = [x, y - x];
}
return ans;
};
golang 解法, 执行用时: 168 ms, 内存消耗: 25.2 MB, 提交时间: 2023-07-21 10:20:01
func findMaxValueOfEquation(points [][]int, k int) int {
ans := math.MinInt
type pair struct{ x, yx int }
q := []pair{}
for _, p := range points {
x, y := p[0], p[1]
for len(q) > 0 && q[0].x < x-k { // 队首超出范围
q = q[1:] // 弹它！
}
if len(q) > 0 {
ans = max(ans, x+y+q[0].yx) // 加上最大的 yi-xi
}
for len(q) > 0 && q[len(q)-1].yx <= y-x { // 队尾不如新来的强
q = q[:len(q)-1] // 弹它！
}
q = append(q, pair{x, y - x})
}
return ans
}
func max(a, b int) int { if b > a { return b }; return a }
cpp 解法, 执行用时: 308 ms, 内存消耗: 88.8 MB, 提交时间: 2023-07-21 10:19:41
class Solution {
public:
int findMaxValueOfEquation(vector<vector<int>> &points, int k) {
int ans = INT_MIN;
deque<pair<int, int>> q;
for (auto &p: points) {
int x = p[0], y = p[1];
while (!q.empty() && q.front().first < x - k) // 队首超出范围
q.pop_front(); // 弹它！
if (!q.empty())
ans = max(ans, x + y + q.front().second); // 加上最大的 yi-xi
while (!q.empty() && q.back().second <= y - x) // 队尾不如新来的强
q.pop_back(); // 弹它！
q.emplace_back(x, y - x);
}
return ans;
}
};
java 解法, 执行用时: 17 ms, 内存消耗: 105 MB, 提交时间: 2023-07-21 10:19:29
class Solution {
public int findMaxValueOfEquation(int[][] points, int k) {
int ans = Integer.MIN_VALUE;
var q = new ArrayDeque<int[]>();
for (var p : points) {
int x = p[0], y = p[1];
while (!q.isEmpty() && q.peekFirst()[0] < x - k) // 队首超出范围
q.pollFirst(); // 弹它！
if (!q.isEmpty())
ans = Math.max(ans, x + y + q.peekFirst()[1]); // 加上最大的 yi-xi
while (!q.isEmpty() && q.peekLast()[1] <= y - x) // 队尾不如新来的强
q.pollLast(); // 弹它！
q.addLast(new int[]{x, y - x});
}
return ans;
}
}
python3 解法, 执行用时: 204 ms, 内存消耗: 53.1 MB, 提交时间: 2023-07-21 10:19:05
# 单调队列
class Solution:
def findMaxValueOfEquation(self, points: List[List[int]], k: int) -> int:
ans = -inf
q = deque()
for x, y in points:
while q and q[0][0] < x - k: # 队首超出范围
q.popleft() # 弹它！
if q:
ans = max(ans, x + y + q[0][1]) # 加上最大的 yi-xi
while q and q[-1][1] <= y - x: # 队尾不如新来的强
q.pop() # 弹它！
q.append((x, y - x))
return ans