LeetCode1340跳跃游戏 V

给你一个整数数组 arr 和一个整数 d 。每一步你可以从下标 i 跳到：
i + x ，其中 i + x < arr.length 且 0 < x <= d 。
i - x ，其中 i - x >= 0 且 0 < x <= d 。
除此以外，你从下标 i 跳到下标 j 需要满足：arr[i] > arr[j] 且 arr[i] > arr[k] ，其中下标 k 是所有 i 到 j 之间的数字（更正式的，min(i, j) < k < max(i, j)）。
你可以选择数组的任意下标开始跳跃。请你返回你 最多 可以访问多少个下标。
请注意，任何时刻你都不能跳到数组的外面。
示例 1：
输入：arr = [6,4,14,6,8,13,9,7,10,6,12], d = 2
输出：4
解释：你可以从下标 10 出发，然后如上图依次经过 10 --> 8 --> 6 --> 7 。
注意，如果你从下标 6 开始，你只能跳到下标 7 处。你不能跳到下标 5 处因为 13 > 9 。你也不能跳到下标 4 处，因为下标 5 在下标 4 和 6 之间且 13 > 9 。
类似的，你不能从下标 3 处跳到下标 2 或者下标 1 处。
示例 2：
输入：arr = [3,3,3,3,3], d = 3
输出：1
解释：你可以从任意下标处开始且你永远无法跳到任何其他坐标。
示例 3：
输入：arr = [7,6,5,4,3,2,1], d = 1
输出：7
解释：从下标 0 处开始，你可以按照数值从大到小，访问所有的下标。
示例 4：
输入：arr = [7,1,7,1,7,1], d = 2
输出：2
示例 5：
输入：arr = [66], d = 1
输出：1
提示：
1 <= arr.length <= 1000
1 <= arr[i] <= 10⁵
1 <= d <= arr.length

动态规划

动态规划的状态表示

dp[i] 表示以arr[i]为起点的最多跳跃次数。
状态数：arr.length

动态规划的转移方程

以左跳为例
dp[i]=max(dp[j]+1),j的范围 { 初始值： i − 1 合法值，非法则停止： ( j > = 0 ) 且 ( i − j ) < = d 且 a r r [ i ] > a r r [ j ] 增量 : j − − \begin{cases}初始值：& i-1\\ 合法值，非法则停止：& (j>=0)且(i-j)<=d 且arr[i] > arr[j] \\ 增量: &j-- \\ \end{cases} ⎩ ⎨ ⎧​初始值：合法值，非法则停止：增量:​i−1(j>=0)且(i−j)<=d且arr[i]>arr[j]j−−​
转移方程时间复杂度：O(arr.length) ，总时间复杂度：O( arr.length $\times$ arr.length)

动态规划的初始值

全为1。

动态规划的填表顺序

arr[i]从小大到

动态规划的返回值

dp的最大值

鸡肋的优化

无论是左跳还是右跳，都只会跳到能跳的最高。但最高可能有多个。比如：
33 1 2 3 左跳到第一个3就无法再跳了。

代码

核心代码

class Solution {
public:
	int maxJumps(vector<int>& arr, int d) {
		multimap<int, int> mValueIndex;
		for (int i = 0; i < arr.size(); i++)
		{
			mValueIndex.emplace(arr[i], i);
		}
		vector<int> dp(arr.size(), 1);
		for (const auto& [tmp, i] : mValueIndex)
		{
			for (int j = i - 1; (j >= 0) && (i - j <= d) && (arr[i] > arr[j]); j--)
			{
				dp[i] = max(dp[i], 1 + dp[j]);
			}
			for (int j = i + 1; (j < arr.size()) && (j-i <= d) && (arr[i] > arr[j]); j++)
			{
				dp[i] = max(dp[i], 1 + dp[j]);
			}
		}
		return *std::max_element(dp.begin(), dp.end());
	}
};

测试用例

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;
	int d;
	{
		Solution sln;
		arr = { 66 }, d = 1;
		auto res = sln.maxJumps(arr, d);
		Assert(1, res);
	}
	{
		Solution sln;
		arr = { 6, 4, 14, 6, 8, 13, 9, 7, 10, 6, 12 }, d = 2;
		auto res = sln.maxJumps(arr, d);
		Assert(4, res);
	}

	{
		Solution sln;
		arr = { 3,3,3,3 }, d = 2;
		auto res = sln.maxJumps(arr, d);
		Assert(1, res);
	}

	{
		Solution sln;
		arr = { 7, 6, 5, 4, 3, 2, 1 }, d = 1;
		auto res = sln.maxJumps(arr, d);
		Assert(7, res);
	}
	{
		Solution sln;
		arr = { 7, 1, 7, 1, 7, 1 }, d = 2;
		auto res = sln.maxJumps(arr, d);
		Assert(2, res);
	}
	
}

2023年2月

class Solution {
public:
int maxJumps(vector& arr, int d) {
m_iNums.assign(arr.size(), -1);
m_vJumpPos.resize(arr.size());
LeftJumpPos(m_vJumpPos, arr, d);
RightJumpPos(m_vJumpPos,arr, d);
for (int i = 0; i < arr.size(); i++)
{
Rec(i);
}
//CConsole::Out(m_vJumpPos, “|”);
//CConsole::Out(m_iNums, “|”);
return *std::max_element(m_iNums.begin(),m_iNums.end());
}
int Rec(int iPos)
{
if (-1 != m_iNums[iPos])
{
return m_iNums[iPos];
}
int iMaxNextNum = 0;
for (const auto& i : m_vJumpPos[iPos])
{
iMaxNextNum = max(iMaxNextNum, Rec(i));
}
return m_iNums[iPos] = iMaxNextNum + 1;
}
vector m_iNums;
void LeftJumpPos(vector<vector>& vLeftJumpPos,const vector& arr, int d)
{
vector vLeftIndexs, vLeftValue;
int iHasDo = 0;
for (int i = 0; i < arr.size(); i++)
{
while ((iHasDo < vLeftIndexs.size()) && (vLeftIndexs[iHasDo] + d < i))
{
iHasDo++;
}
auto it = std::upper_bound(vLeftValue.begin() + iHasDo, vLeftValue.end(), arr[i], std::greater());
if (vLeftValue.end() == it)
{
}
else
{
for (auto ij = it; (ij != vLeftValue.end()) && (*it == *ij); ++ij)
{
int index = ij - vLeftValue.begin();
vLeftJumpPos[i].push_back(vLeftIndexs[index]);
}
}
while ((vLeftValue.size() > iHasDo) && (arr[i] > vLeftValue.back()))
{
vLeftIndexs.pop_back();
vLeftValue.pop_back();
}
vLeftIndexs.push_back(i);
vLeftValue.push_back(arr[i]);
}
}
void RightJumpPos(vector<vector>& vJumpPos, const vector& arr, int d)
{
vector vIndexs, vValue;
int iHasDo = 0;
for (int i = arr.size() - 1; i >= 0; i–)
{
while ((iHasDo < vIndexs.size()) && (vIndexs[iHasDo] - d > i))
{
iHasDo++;
}
auto it = std::upper_bound(vValue.begin() + iHasDo, vValue.end(), arr[i], std::greater());
if (vValue.end() == it)
{
}
else
{
for (auto ij = it; (ij != vValue.end()) && (*it == *ij);++ij)
{
int index = ij - vValue.begin();
vJumpPos[i].push_back(vIndexs[index]);
}
}
while ((vValue.size() > iHasDo) && (arr[i] > vValue.back()))
{
vIndexs.pop_back();
vValue.pop_back();
}
vIndexs.push_back(i);
vValue.push_back(arr[i]);
}
}
vector<vector> m_vJumpPos;
};

2023年7月版

class Solution {
public:
int maxJumps(vector& arr, int d) {
m_c = arr.size();
m_d = d;
vector<vector> vLeft,vRight,vMove(m_c);
GetLeft(vLeft, arr);
GetRight(vRight, arr);
for (int i = 0; i < m_c; i++)
{
vMove[i].insert(vMove[i].end(), vLeft[i].begin(), vLeft[i].end());
const int right = m_c - 1 - i;
vMove[i].insert(vMove[i].end(), vRight[right].begin(), vRight[right].end());
}
//值从小到大出来
std::multimap<int, int> mValueIndexs;
for (int i = 0; i < arr.size(); i++)
{
mValueIndexs.emplace(arr[i], i);
}
vector vRet(m_c, -1);
for (const auto& it : mValueIndexs)
{
int iCanMove = 0;
for (const auto& next : vMove[it.second])
{
iCanMove = max(iCanMove, vRet[next]);
}
vRet[it.second] = iCanMove+1;
}
return *std::max_element(vRet.begin(), vRet.end());
}
void GetLeft(vector<vector>& vMove, const vector& arr)
{
std::stack sta;
for (int i = 0; i < arr.size(); i++)
{
int iMoveValue = -1;
vMove.emplace_back();
while (sta.size() && (arr[()] < arr[i]))
{
const int iTop = ();
sta.pop();
if (abs(iTop - i) <= m_d)
{
if (arr[iTop] != iMoveValue)
{
vMove.back().clear();
}
vMove.back().emplace_back(iTop);
iMoveValue = arr[iTop];
}
}
sta.emplace(i);
}
}
void GetRight(vector<vector>& vMove, const vector& arr)
{
std::stack sta;
for (int i = m_c - 1; i >= 0; i–)
{
int iMoveValue = -1;
vMove.emplace_back();
while (sta.size() && (arr[()] < arr[i]))
{
const int iTop = ();
sta.pop();
if (abs(iTop - i) <= m_d)
{
if (arr[iTop] != iMoveValue)
{
vMove.back().clear();
}
vMove.back().emplace_back(iTop);
iMoveValue = arr[iTop];
}
}
sta.emplace(i);
}
}
int m_c;
int m_d;
};

2023年8月版

class Solution {
public:
int maxJumps(vector& arr, int d) {
m_c = arr.size();
m_arr = arr;
m_iD = d;
m_vCanMove.resize(m_c);
DoLeft();
DoRight();
std::multimap<int, int> mHeightIndex;
for ( int i = 0; i < m_c; i++)
{
mHeightIndex.emplace(arr[i], i);
}
vector vRet(m_c);
for (const auto& it : mHeightIndex)
{
int iPre = 0;
for (const int pr : m_vCanMove[it.second])
{
iPre = max(iPre, vRet[pr]);
}
vRet[it.second] = iPre + 1;
}
return *std::max_element(vRet.begin(), vRet.end());
}
void DoLeft()
{
stack sta;
for (int i = 0; i < m_c; i++)
{
vector vCanMove;
while (sta.size() && (m_arr[()] < m_arr[i]))
{
if (abs(() - i) <= m_iD)
{
vCanMove.emplace_back(());
}
sta.pop();
}
if (vCanMove.size())
{
const int iMax = m_arr[vCanMove.back()];
for (int j = vCanMove.size() - 1; (j >= 0)&&(iMax == m_arr[vCanMove[j]]); j–)
{
m_vCanMove[i].emplace_back(vCanMove[j]);
}
}
sta.emplace(i);
}
}
void DoRight()
{
stack sta;
for (int i = m_c-1 ; i >= 0 ; i–)
{
vector vCanMove;
while (sta.size() && (m_arr[()] < m_arr[i]))
{
if (abs(() - i) <= m_iD)
{
vCanMove.emplace_back(());
}
sta.pop();
}
if (vCanMove.size())
{//只需要考虑移动到次高，如果有多个次高可以一定，全部要考虑
const int iMax = m_arr[vCanMove.back()];
for (int j = vCanMove.size() - 1; (j >= 0) && (iMax == m_arr[vCanMove[j]]); j–)
{
m_vCanMove[i].emplace_back(vCanMove[j]);
}
}
sta.emplace(i);
}
}
vector<vector> m_vCanMove;
vector m_arr;
int m_iD;
int m_c;
};