题目

给你一个数组 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 的点。

思路

考虑公式
$y_i + y _j+\left|x_i - x_j\right|$

等价于
$x_j + y_j +(y_i - x_i) = x_j + y_j + t_i$

因此对于$j$ 前面的 k 个数字, 寻找最大的$y_i - x_i$ 即可, 使用优先队列.

代码如下

class Solution {
public:int findMaxValueOfEquation(vector<vector<int>>& points, int k) {typedef pair<int, int > PII;priority_queue<PII> q;// yj + xj + yi - xiint ret = INT_MIN;for(auto point: points){if(q.empty()) q.push(make_pair(point[1] - point[0], point[0]));else{int cur_sum = point[0] + point[1];// cout << q.top().second << endl;while(!q.empty() && point[0] - q.top().second > k) q.pop();if(!q.empty()){ret = max(ret, q.top().first + cur_sum);}q.push(make_pair(point[1] - point[0], point[0]));}}return ret;}
};