【单调队列】LeetCode1499:满足不等式的最大值

2023-12-26 14:06:59

涉及知识点

单调队列

题目

给你一个数组 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<j的情况。(i,j)和(j,i)本质是一样的。
由于x是升序,所以xi <= xj,也就是:yi+yj+|xi-xj| 等于yi+yj+xj-xi ,xj+yj合并 yi-xi合并,简称subi。
将xi和yi-xi放到双向队列中。
淘汰以下数据:
一,xj-xi >k,从队首淘汰。
二,i1 <i2,且subi1< subi2。如果j能选择i1,则必定能选择i2。subi大则yi+yj+xj-xi大。从队尾淘汰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++ 实现。

文章来源:https://blog.csdn.net/he_zhidan/article/details/135172204
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。