【栈】B020

一、Problem

给定一个整数数组 A，坡是元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这样的坡的宽度为 j - i。

找出 A 中的坡的最大宽度，如果不存在，返回 0 。

输入：[6,0,8,2,1,5] 输出：4 解释： 最大宽度的坡为 (i, j) = (1, 5): A[1] = 0 且 A[5] = 5.

提示：

2 <= A.length <= 50000 0 <= A[i] <= 50000

二、Solution

方法一：排序

思路

注：我们只关心下标的差值吧，所以我们需要一堆下标而并不需要值，所以我们只需要对数组下标按照权值升序排序，然后记录遍历途中的最小下标即可

class Solution { public: int maxWidthRamp(vector<int>& A) { int n = A.size(); vector<int> B(n); for (int i = 0; i < n; i++) B[i] = i; sort(B.begin(), B.end(), [&](int i, int j){ if (A[i] == A[j]) return i < j; return A[i] < A[j]; }); int midx = n+50, maxv = 0; for (int x : B) { maxv = max(maxv, x-midx); midx = min(midx, x); } return maxv; } };

复杂度分析

时间复杂度：$O(nlogn)$，空间复杂度：$O(n)$，

---

方法二：单调栈

思路

我们希望在遍历某一个元素 A[i] 时，能快速地找到一个比A[i] 小的，且在 i 位置左边的元素，基于这一点，我们可维护一个权值对应的下标单调递减的栈

我们希望坡度最大，所以我们从右往左枚举，这样可以尽量让我们计算得到的结果最大

细节：当当前遍历下标 i 小于当前最大坡度 ans，那么无论栈中元素是多少，产生的新坡度都不会大于 ans，故可提前结束遍历

class Solution { public: int maxWidthRamp(vector<int>& A) { int n = A.size(), ans = 0; stack<int> st; for (int i = 0; i < n; i++) { if (st.empty() || A[i] <= A[st.top()]) st.push(i); } for (int i = n-1; i > ans; i--) { while (!st.empty() && A[st.top()] <= A[i]) { ans = max(ans, i - st.top()); st.pop(); } } return ans; } };

复杂度分析

时间复杂度：$O(n)$，空间复杂度：$O(n)$，