网站建设技术交流,十大放黄不登录不收费,wordpress页面显示分类,企业搭建网站的必要性1499. 满足不等式的最大值
给你一个数组 points 和一个整数 k 。数组中每个元素都表示二维平面上的点的坐标#xff0c;并按照横坐标 x 的值从小到大排序。也就是说 points[i] [xi, yi] #xff0c;并且在 1 i j points.length 的前提下#xff0c; xi 并按照横坐标 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^8对于所有的1 i j points.length points[i][0] points[j][0] 都成立。也就是说xi 是严格递增的。 解题思路 使用优先队列作为一个滑动窗口 持续更新求解目标的最大值在一个长度位k的窗口中找到满足 yiyj|xi-xj| 就是变换形式的xj-xiyiyj 形式
官方如下
class Solution {
public:using piipairint ,int ; //定义一个别名 pii存储两个有序的值像坐标xyint findMaxValueOfEquation(vectorvectorint points, int k) {int resINT_MIN; //初始化一个最小值priority_queuepii,vectorpii,greaterpii heap; //创建一个优先队列 这是最小堆 其中pair为排序的关键 本体的第一项是有序的for(auto point: points) //进行遍历poines中的元素{int xpoint[0],ypoint[1]; //进行判断如果当前元素与栈顶第一项的差值大于k时就将栈顶元素推出 // 然后在进行判断 直到当前值与前一个元素差值小于k那么就满足条件while(!heap.empty()x-heap.top().secondk)heap.pop();//更新最大值if(!heap.empty()){resmax(res,xy-heap.top().first);}//将当前元素入栈heap.emplace(make_pair(x-y,x));}return res;}
}; 在加一个解法采用算双端队列来存储点的索引
class Solution {
public:int findMaxValueOfEquation(vectorvectorint points, int k) {dequeint dq; // 创建双端队列dq来存储点的索引int result INT_MIN; // 记录最大值for(int i 0; i points.size(); i){ // 遍历数组pointswhile(!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; // 返回最大值作为结果}
};
