map|动态规划|单调栈|975:奇偶跳

作者推荐

视频算法专题

本文涉及的基础知识点

单调栈分类、封装和总结
动态规划汇总

题目

给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5… 次跳跃称为奇数跳跃，而第 2、4、6… 次跳跃称为偶数跳跃。
你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：
在进行奇数跳跃时（如，第 1，3，5… 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
在进行偶数跳跃时（如，第 2，4，6… 次跳跃），你将会跳到索引 j，使得 A[i] >= A[j]，A[j] 是可能的最大值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
（对于某些索引 i，可能无法进行合乎要求的跳跃。）
如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。
返回好的起始索引的数量。
示例 1：
输入：[10,13,12,14,15]
输出：2
解释：
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
示例 2：
输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：
在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。
在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。
在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。
我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。
类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
示例 3：
输入：[5,1,3,4,2]
输出：3
解释：
我们可以从起始索引 1，2，4 出发到达数组末尾。
提示：
1 <= A.length <= 20000
0 <= A[i] < 100000

代码

单调栈

此方法比map巧妙，性能差不多，值得学习。时间复杂度：O(nlogn)。

变量函数解析

indexs	计算奇数跳时，arr[index[i]] 升序，且相等的元素，相对顺序不变。计算偶数跳时，arr[index[i]] 降序，且相等的元素，相对顺序不变。
Next	计算奇（偶）数跳的下一个位置，如果无法跳，则值为m_c
vStatus	记录偶数（奇数）跳能否跳到队尾。vStatus[0][m_c]和vStatus[0][m_c]为false，避免处理边界条件

Next奇数跳为例

令j=index[jj],按jj从小到的顺序，将j入栈，由于arr[index[jj]]是升序，所以：规则一：arr[栈中元素] <=arr[j]。
(sta.top() < j 成立，说明：
规则二：j在sta.top()右边。
规则三：令index[jj2] 为sta.top(),arr[index(jj2,j)]中的数（即大于等于arr[sta.top()] 同时小于等于arr[j]的数）全部在sta.top()的左边，否则出栈了。
结合规则一二三，stat.top()的下一步就是j。

核心代码

class Solution { public: 	int oddEvenJumps(vector<int>& arr) { 		m_c = arr.size(); 		vector<int> indexs(m_c); 		iota(indexs.begin(), indexs.end(), 0); 		sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return (arr[i1] < arr[i2]) || ((arr[i1] == arr[i2]) && (i1 < i2)); }); 		const auto& v1 = Next(indexs); 		sort(indexs.begin(), indexs.end(), [&](const int i1, const int i2) {return (arr[i1] > arr[i2]) || ((arr[i1] == arr[i2]) && (i1 < i2)); }); 		const auto& v2 = Next(indexs);  		vector<vector<bool>> vStatus(2, vector<bool>(m_c+1)); 		int iRet = 1; 		vStatus[0][m_c-1] = true; 		vStatus[1][m_c - 1] = true; 		for (int i = m_c - 1 - 1; i >= 0; i--) 		{ 			vStatus[0][i] = vStatus[1][v2[i]];//偶数跳 			vStatus[1][i] = vStatus[0][v1[i]];//奇数跳 			iRet +=  (int)vStatus[1][i]; 		} 		return iRet; 	} 	vector<int> Next(const vector<int>& indexs) 	{ 		vector<int> vNext(indexs.size(), indexs.size()); 		stack<int> sta; 		for (int j : indexs) 		{ 			while (sta.size() && (sta.top() < j)) 			{ 				vNext[sta.top()] = j; 				sta.pop(); 			} 			sta.emplace(j); 		} 		return vNext; 	} 	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<int> arr; 	{ 		Solution slu; 		arr = { 10,13,12,14,15 }; 		auto res = slu.oddEvenJumps(arr); 		Assert(2, res); 	} 	{ 		Solution slu; 		arr = { 2,3,1,1,4 }; 		auto res = slu.oddEvenJumps(arr); 		Assert(3, res); 	} 	{ 		Solution slu; 		arr = { 5,1,3,4,2 }; 		auto res = slu.oddEvenJumps(arr); 		Assert(3, res); 	} 	 	 	//CConsole::Out(res); } 

2023年2月3 单调栈

换汤不换药，方便理解上面的算法。
我们将值和下标放到大根堆中，从最大值到最小值出堆，值相同下标大的先出。
我们将值和下标放到小根堆中，从最小值到最大值出堆，值相同下标大的先出（需要将索引设置成负数）。
不失一般性以奇数跳来说明。
按出堆顺序，放到栈中。栈中的j，全部符合arr[j]>=arr[i]，且从到尾越来越小。如果栈顶（尾）的元素jj0大于栈中的元素j1。则j0被淘汰。 如果j1>i，则j0>i。而arr[j0] <= arr[j1]，arr[j1]被淘汰。淘汰后，从容器头到容器尾：值越来越小，下标j越来越小。下标j越来越小,这意味者淘汰时遇到不用淘汰的，后面都不用淘汰。显然i入栈前的栈顶元素，就是i 奇数跳下标。
vRet[0]有m_c+1个元素，最后一个元素指向非法下标。

class Solution { public: 	int oddEvenJumps(vector<int>& arr) { 		m_c = arr.size(); 		priority_queue<pair<int, int>, vector<pair<int, int>>, less<pair<int, int>>> maxHeap; 		priority_queue<pair<int, int>,vector<pair<int, int>>, greater<pair<int, int>>> minHeap; 		for (int i = 0; i < arr.size(); i++) 		{ 			maxHeap.emplace(arr[i], i); 			minHeap.emplace(arr[i], -i); 		} 		vector<vector<int>> vRet(2,vector<int>(m_c+1, 0)); 		vRet[0][m_c-1] = vRet[1][m_c - 1] = 1; 		vector<int> vNext0(m_c, m_c), vNext1(m_c, m_c); 		Next(vNext0, maxHeap); 		Next(vNext1, minHeap); 		for (int i = m_c - 2; i >= 0; i--) 		{	 			vRet[0][i] = vRet[1][vNext0[i]]; 			vRet[1][i] = vRet[0][vNext1[i]]; 		} 		return std::accumulate(vRet[0].begin(),vRet[0].end(),0); 	}	 	template<class T> 	void Next(vector<int>& vNext, T& heap) 	{ 		stack<int> sta; 		while (heap.size()) 		{ 			auto [tmp, index] = heap.top(); 			index = abs(index); 			heap.pop(); 			while (sta.size() && (index > sta.top())) 			{ 				sta.pop(); 			} 			if (sta.size()) 			{ 				vNext[index] = sta.top(); 			} 			sta.emplace(index); 		} 	} 	int m_c; }; 

2023年3月版：map

利用map性能和单调栈差不多，好理解。从后向前遍历各元素，map的键对应arr[i]，map的值对应i。如果arr[i]，i小的（后加入的）覆盖前面的。
时间复杂度：O(nlogn)。

map

map可以分成有序(单调)map和无序(哈希)map。还可分成单键map和多键map（允许重复的键）。

 class Solution {  public: 	 int oddEvenJumps(vector<int>& arr) { 		 vector<vector<bool>> result; 		 result.assign(arr.size(), vector<bool>(2)); 		 result[arr.size() - 1][0] = true; 		 result[arr.size() - 1][1] = true; 		 std::map<int, int> mValueIndex; 		 mValueIndex[arr.back()] = arr.size()-1; 		 for (int i = arr.size() - 2; i >= 0; i--) 		 { 			 {//奇数跳跃 				 auto it = mValueIndex.lower_bound(arr[i]); 				 if (mValueIndex.end() != it) 				 { 					 result[i][0] = result[it->second][1]; 				 } 			 } 			 {//偶数跳跃 			 auto it2 = mValueIndex.upper_bound(arr[i]); 			 if (mValueIndex.begin() != it2) 			 { 				 --it2; 				 result[i][1] = result[it2->second][0]; 			 } 			 mValueIndex[arr[i]] = i; 		 } 		 } 		 int iNum = 0; 		 for (int i = 0; i < arr.size(); i++) 		 { 			 if (result[i][0]) 			 { 				 iNum++; 			 } 		 } 		 return iNum; 	 }  }; 

2024年2月3号

可以直接求和。

class Solution { public: 	int oddEvenJumps(vector<int>& arr) { 		m_c = arr.size(); 		vector<vector<int>> vRet(2,vector<int>(m_c, 0)); 		vRet[0].back() = vRet[1].back() = 1; 		map<int, int> mValueToIndex; 		mValueToIndex[arr.back()] = m_c - 1; 		for (int i = m_c - 2; i >= 0; i--) 		{	 			{ 				auto it = mValueToIndex.lower_bound(arr[i]); 				if (mValueToIndex.end() != it) 				{ 					vRet[0][i] = vRet[1][it->second]; 				} 			} 			{ 				auto it = mValueToIndex.upper_bound(arr[i]); 				if (mValueToIndex.begin() != it) 				{ 					vRet[1][i] = vRet[0][(--it)->second]; 				} 			} 			mValueToIndex[arr[i]] = i; 		} 		return std::accumulate(vRet[0].begin(),vRet[0].end(),0); 	}	 	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++ 实现。