涉及知识点
单调队列
题目
给你一个数组 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 <= 105
points[i].length == 2
-108 <= points[i][0], points[i][1] <= 108
0 <= k <= 2 * 108
对于所有的1 <= i < j <= points.length ，points[i][0] < points[j][0] 都成立。也就是说，xi 是严格递增的。
单调队列
枚举j，计算i。我们只考虑i
由于x是升序，所以xi <= xj，也就是：yi+yj+|xi-xj| 等于yi+yj+xj-xi ，xj+yj合并 yi-xi合并,简称subi。
将xi和yi-xi放到双向队列中。
淘汰以下数据：
一，xj-xi >k，从队首淘汰。
二,i1
代码
核心代码
class Solution { public: int findMaxValueOfEquation(vector<vector<int>>& points, int k) { m_c = points.size(); deque<pair<int, int>> mXSub; int iRet = INT_MIN; for (int i = 0; i < m_c; i++) { while (mXSub.size() && (points[i][0] - mXSub.front().first > k)) { mXSub.pop_front(); } if (mXSub.size()) { iRet = max(iRet, mXSub.front().second + points[i][0] + points[i][1]); } while (mXSub.size() && (mXSub.back().second <= points[i][1] - points[i][0])) { mXSub.pop_back(); } mXSub.emplace_back(points[i][0], points[i][1] - points[i][0]); } return iRet; } int m_c; };
测试用例
template<class T> void Assert(const T& t1, const T& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { vector<vector<int>> points; int k; { Solution sln; points = { {1,3},{2,0},{5,10},{6,-10} }, k = 1; auto res = sln.findMaxValueOfEquation(points, k); Assert(4, res); } { Solution sln; points = { {0,0},{3,0},{9,2} }, k = 3; auto res = sln.findMaxValueOfEquation(points, k); Assert(3, res); } //CConsole::Out(res); }
2023年3月旧代码
class Solution { public: int findMaxValueOfEquation(vector<vector<int>>& points, int k) { m_c = points.size(); std::map<int,std::set<int>> mYSubXToX,mXToYSubX; int iMax = INT_MIN; for (int i = 0; i < m_c; i++ ) { const vector<int>& pt = points[i]; //删除x的差的绝对值大于k while (mXToYSubX.size() && ((mXToYSubX.begin()->first + k) < pt[0])) { for (const auto& ySubX : mXToYSubX.begin()->second) { mYSubXToX[ySubX].erase(mXToYSubX.begin()->first); if (mYSubXToX[ySubX].empty()) { mYSubXToX.erase(ySubX); } } mXToYSubX.erase(mXToYSubX.begin()); } if (mYSubXToX.size()) { iMax = max(iMax, mYSubXToX.rbegin()->first + pt[0] + pt[1]); } const int iYSubX = pt[1] - pt[0]; mXToYSubX[pt[0]].insert(iYSubX); mYSubXToX[iYSubX].insert(pt[0]); } return iMax; } int m_c; };
扩展阅读
视频课程
有效学习：明确的目标 及时的反馈 拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771
如何你想快
速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176
相关
下载
想高屋建瓴的学习算法，请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653
测试环境
操作系统：win7 开发环境： VS2019 C++17
或者 操作系统：win10 开发环境： VS2022 C++17
如无特殊说明，本算法用C++ 实现。
