【单调栈】2289. 使数组按非递减顺序排列

本文涉及的基础知识点

单调栈分类、封装和总结

LeetCode2289. 使数组按非递减顺序排列

给你一个下标从 0 开始的整数数组 nums 。在一步操作中，移除所有满足 nums[i - 1] > nums[i] 的 nums[i] ，其中 0 < i < nums.length 。
重复执行步骤，直到 nums 变为非递减数组，返回所需执行的操作数。
示例 1：
输入：nums = [5,3,4,4,7,3,6,11,8,5,11]
输出：3
解释：执行下述几个步骤：

步骤 1 ：[5,3,4,4,7,3,6,11,8,5,11] 变为 [5,4,4,7,6,11,11]
步骤 2 ：[5,4,4,7,6,11,11] 变为 [5,4,7,11,11]
步骤 3 ：[5,4,7,11,11] 变为 [5,7,11,11]
[5,7,11,11] 是一个非递减数组，因此，返回 3 。
示例 2：
输入：nums = [4,5,7,7,13]
输出：0
解释：nums 已经是一个非递减数组，因此，返回 0 。
提示：
1 <= nums.length <= 10⁵
1 <= nums[i] <= 10⁹

单调栈

$\forall$ i,j ,i < j ，且nums[i] > nums[j] 则nums[j]必定被删除。性质一，下面来证明：
如果有多个符合的i，取最大的。即 $\forall k \in (i,j)$ nums[k] <= nums[j] ,即：nums[i]会删除所有nums[k]后，再删除nums[j]。
会不会存在如下情况：nums[i]被nums[m]删除，会。但nums[j]会被nums[m]删除。
如果nums[i]没有被删除，则nums[j]需要j-i次删除。
如果nums[i]被删除，也是。假设i删除k1的同时被删除,此是m在k1的位置；如果nums[i]没被删除，此刻i也在k1位置。
j从小到大枚举nums[j]，栈sta记录 nums[0…j-1]的值和下标。
寻找i的逻辑：大于nums[j]且下标最大。那值小于等于nums[j]，且下标小于j的被淘汰。淘汰后：
一，下标升序。
二，值降序。
三，栈中所有值大于nums[j]
如果栈非空：nums[j]需要删除 j - sta.top().second
取最大值，如果 $\forall j$ 的栈都为空，则结果为0

思路错误

15 2 13 1 可以同时删除，15删除2时，13删除1。
错误代码

class Solution {
public:int totalSteps(vector<int>& nums) {stack<pair<int, int>> sta;int ret = 0;for (int j = 0; j < nums.size(); j++) {while (sta.size() && (sta.top().first <= nums[j])) {sta.pop();}if (sta.size()) {ret = max(ret, j - sta.top().second);}sta.emplace(nums[j], j);}return ret;}
};

换个错误的思路

如果不存在i，ret[j]为0。
如果nums[i-1] > nums[i] ret[i]为1。
否则 ret[i] = ret[i-1]。
错误原因：num[m1] 删除nums[i-1] 因为小于等于nums[i] 无法删除nums[i]

class Solution {
public:int totalSteps(vector<int>& nums) {stack<tuple<int, int,int>> sta;vector<int> ret;for (int j = 0; j < nums.size(); j++) {while (sta.size() && (get<0>(sta.top()) <= nums[j])) {sta.pop();	}if (sta.size()) {if (nums[j - 1] > nums[j]) {ret.emplace_back(1);}else {ret.emplace_back(ret.back() + 1);}}else {ret.emplace_back(0);}sta.emplace(nums[j], j,0);}return *  std::max_element(ret.begin(), ret.end());}
};

正确思路

如果是nums[m2]删除nums[m1]，且nums[m2]>nums[i]，则ret[i] = ret[m1]+1否则：
由于是nums[m3]删除nums[m1]，且nums[m3]> nums[i] 故vet[i] >= ret[m2]+1,否则：
$\vdots$
我们只需要求m1 … m2等的最大值。
我们假定nums[j]被nums[i]所删除，则：在nums[j]被删除前，nums[i+1…j-1]都已经被删除。
ret[j]一定等于 ret[i+1…j-1]的最大值+1。
令 i < k1 <k2 < j。如果nums[k1]被 nums[k2]淘汰，不影响最终结果。因为：
因为nums[k1]无法淘汰nums[k2]，nums[m]淘汰nums[k2]必须先淘汰nums[k1]，故ret[k1] 一定小于ret[k2]

代码

class Solution {
public:int totalSteps(vector<int>& nums) {stack<pair<int,int>> sta;int ret = 0;for (int j = 0; j < nums.size(); j++) {int iMax = 0;while (sta.size() && (sta.top().first <= nums[j])) {iMax = max(iMax, sta.top().second);sta.pop();	}int cnt = sta.empty() ? 0 : (iMax + 1);		ret = max(ret, cnt);sta.emplace(nums[j],cnt);}return ret;}
};

单元测试

template<class T1, class T2>
void AssertEx(const T1& t1, const T2& t2)
{Assert::AreEqual(t1, t2);
}
void AssertEx( double t1,  double t2)
{auto str = std::to_wstring(t1) + std::wstring(1,32) + std::to_wstring(t2);Assert::IsTrue(abs(t1 - t2) < 1e-5,str.c_str() );
}template<class T>
void AssertEx(const vector<T>& v1, const vector<T>& v2)
{Assert::AreEqual(v1.size(), v2.size());for (int i = 0; i < v1.size(); i++){Assert::AreEqual(v1[i], v2[i]);}
}template<class T>
void AssertV2(vector<vector<T>> vv1, vector<vector<T>> vv2)
{sort(vv1.begin(), vv1.end());sort(vv2.begin(), vv2.end());Assert::AreEqual(vv1.size(), vv2.size());for (int i = 0; i < vv1.size(); i++){AssertEx(vv1[i], vv2[i]);}
}namespace UnitTest
{vector<int> nums;TEST_CLASS(UnitTest){public:TEST_METHOD(TestMethod00){nums = { 5, 3, 4, 4, 7, 3, 6, 11, 8, 5, 11 };auto res = Solution().totalSteps(nums);AssertEx(3, res);}TEST_METHOD(TestMethod01){nums = { 4,5,7,7,13 };auto res = Solution().totalSteps(nums);AssertEx(0, res);}TEST_METHOD(TestMethod02){nums = { 5,14,15,2,11,5,13,15 };auto res = Solution().totalSteps(nums);AssertEx(3, res);}TEST_METHOD(TestMethod03){nums = { 7,14,4,14,13,2,6,13 };auto res = Solution().totalSteps(nums);AssertEx(3, res);}TEST_METHOD(TestMethod04){nums = { 10,1,2,3,4,5,6,1,2,3 };auto res = Solution().totalSteps(nums);AssertEx(6, res);}};
}

扩展阅读

视频课程

先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛