【C++单调栈】962. 最大宽度坡|1607

本文涉及的基础知识点

C++单调栈

LeetCode962. 最大宽度坡

给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。
找出 A 中的坡的最大宽度，如果不存在，返回 0 。
示例 1：
输入：[6,0,8,2,1,5]
输出：4
解释：
最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.
示例 2：
输入：[9,8,1,0,1,9,4,0,4,1]
输出：7
解释：
最大宽度的坡为 (i, j) = (2, 9): A[2] = 1 且 A[9] = 1.
提示：
2 <= A.length <= 50000
0 <= A[i] <= 50000

单调栈

如果i1<i2,且A[i1] <= A[i2], $\forall$ j ,j >i2，(i2,j)一定不是最优坡，因为(i1,j)更优。
故：只有nums[i] 小于栈顶元素才可能是最优i。这样栈底到栈顶是严格降序。
j从大到小枚举nums[j]，
从栈顶到栈底，只有一个nums[stack.top()] <= nums[j] ，便是j的最优i，令其为i1。i1被j出栈不会影响(i1,x)，i1被j出栈说明，不存在(i1,x) 且x > j的解。 x< j的解，显然劣于(i1,j)

代码

核心代码

class Solution {public:int maxWidthRamp(vector<int>& nums) {vector<int> sta = { 0 };for (int i = 1; i < nums.size(); i++) {if (nums[i] < nums[sta.back()]) {sta.emplace_back(i);}}int ret = 0;for (int i = nums.size() - 1; i >= 0; i--) {while (sta.size() && (nums[sta.back()] <= nums[i])) {ret = max(ret, i - sta.back());sta.pop_back();}}return ret;}};

单元测试

vector<int> nums;TEST_METHOD(TestMethod11){nums = { 6,0,8,2,1,5 };auto res = Solution().maxWidthRamp(nums);AssertEx(4, res);}TEST_METHOD(TestMethod12){nums = { 9,8,1,0,1,9,4,0,4,1 };auto res = Solution().maxWidthRamp(nums);AssertEx(7, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功