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^5
- points[i].length == 2
- -10^8 <= points[i][0], points[i][1] <= 10^8
- 0 <= k <= 2 * 10^8
- 对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。
解题思路 使用优先队列作为一个滑动窗口 持续更新求解目标的最大值，在一个长度位k的窗口中找到满足 yi+yj+|xi-xj| 就是变换形式的xj-xi+yi+yj 形式
官方如下
class Solution { public: using pii=pair<int ,int >; //定义一个别名 pii存储两个有序的值，像坐标（x，y） int findMaxValueOfEquation(vector<vector<int>>& points, int k) { int res=INT_MIN; //初始化一个最小值 priority_queue<pii,vector<pii>,greater<pii>> heap; //创建一个优先队列 这是最小堆 其中pair为排序的关键 本体的第一项是有序的 for(auto& point: points) //进行遍历poines中的元素 { int x=point[0],y=point[1]; //进行判断如果当前元素与栈顶第一项的差值大于k时就将栈顶元素推出 ， // 然后在进行判断 直到当前值与前一个元素差值小于k那么就满足条件 while(!heap.empty()&&x-heap.top().second>k) heap.pop(); //更新最大值 if(!heap.empty()) { res=max(res,x+y-heap.top().first); } //将当前元素入栈 heap.emplace(make_pair(x-y,x)); } return res; } };
在加一个解法采用算双端队列来存储点的索引
class Solution { public: int findMaxValueOfEquation(vector<vector<int>>& points, int k) { deque<int> dq; // 创建双端队列dq来存储点的索引 int result = INT_MIN; // 记录最大值 for(int i = 0; i < points.size(); i++){ // 遍历数组points while(!dq.empty() && points[dq.front()][0] + k < points[i][0]) dq.pop_front(); // 如果当前点的横坐标与队首点的横坐标差超过k，则移除队首点 if(!dq.empty()){ int xj = points[i][0]; // 获取当前点的横坐标 int yi = points[i][1]; // 获取当前点的纵坐标 int xi = points[dq.front()][0]; // 获取队首点的横坐标 int yj = points[dq.front()][1]; // 获取队首点的纵坐标 result = max(result, yi + yj + xj - xi); // 更新最大值 } while(!dq.empty() && points[i][1] - points[i][0] >= points[dq.back()][1] - points[dq.back()][0]) dq.pop_back(); // 移除双端队列尾部所有纵坐标较小的点 dq.push_back(i); // 将当前点的索引插入双端队列尾部 } return result; // 返回最大值作为结果 } };
