题目
题目来源：力扣（LeetCode）
给你一个数组 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 。
思路分析
思路一：转换成求区间最大值问题
问题要求解 y(i) + y(j) + |x(i) - x(j)| 的最大值。
由于给定的 points 数组横坐标 x 是从小到大排列的。所以，如果我们保证我们搜索的两个点，points[i] 在 points[j] 的前面，就一定有 x(i) - x(j) < 0。
所以，|x(i) - x(j)| = x(j) - x(i)。
所以，y(i) + y(j) + |x(i) - x(j)| = y(i) + y(j) + x(j) - x(i) = (y(i) - x(i)) + (y(j) + x(j)).
问题就变成了，找到两个点，点 points[i] 的 y(i) - x(i) 和点 points[j] 的 y(j) + x(j) 的和最大。
限制条件是，x(i) <= x(j) 且最大相差 k。
因此，我们可以扫描所有的点，对于每一个点，看前面的点中，只要横坐标相差没有超过 k，其中最大的 y(i) - x(i) 是多少。
我们把问题转换成为了一个求区间最大值的问题。
可以使用一个单调队列来获得区间最大值，队列中存储坐标点， 保持队列单调递减，保证队列头部就是队列中最大的 yi-xi 。
具体地：
- 定义结果值ans和一个队列que，遍历points
- 如果当前的x坐标与队首元素相比，如果大于k的话将队首元素出队
- 然后和处理过的队列的队首元素用公式求值，和ans取较大值再赋值给ans
- 然后和队尾元素比较yi-xi的值，如果大于队尾元素，则队尾元素出队
- 最后当前元素进队列
代码：
/*** @param {number[][]} points* @param {number} k* @return {number}*/var findMaxValueOfEquation = function (points, k) {let len = points.length,max = -Infinity,queue = [];for (let j = 0; j < len; j++) {let [xj, yj] = points[j];// 把队列头部不满足条件 |xi - xj| <= k 的元素 shift 掉while (queue.length > 0 && xj - queue[0][0] > k) queue.shift();// 更新最大值if (queue.length > 0) {max = Math.max(queue[0][1] - queue[0][0] + xj + yj, max);}// 在把当前的 points[j] push 加入到队尾之前，把队列尾部比 points[j] 的 yj-xj// 小的元素 pop 掉，保证队列单调递减while (queue.length > 0 && (queue[queue.length - 1][1] - queue[queue.length - 1][0]) < (yj - xj)) queue.pop();queue.push(points[j]);}return max;};
若有收获，就点个赞吧
0 人点赞
