LeetCode 962中等单调栈/双指针
最大宽度坡 图解题解
这道题到底在问什么
给定数组 nums。若 i < j 且 nums[i] ≤ nums[j]，则 (i,j) 是一个坡，宽度 j−i。返回最大坡宽;不存在返回 0。
- 输入
- nums=[6,0,8,2,1,5]
- 输出
- 4 （i=1, j=5：0 ≤ 5，宽 4）
最优解：一步一步想明白
- 3记住「左建递减候选栈，右扫能配就弹栈取最宽」，下面每帧都在套它。
- 4第 0 个 9 直接入栈，作为第一个候选左端点(蓝色)。
- 58 比栈顶值 9 还小，刷新出值更小的新候选左端点(它下标更靠右、但值更小)，入栈(蓝色)。
- 61 比栈顶值 8 还小，刷新出值更小的新候选左端点(它下标更靠右、但值更小)，入栈(蓝色)。
- 70 比栈顶值 1 还小，刷新出值更小的新候选左端点(它下标更靠右、但值更小)，入栈(蓝色)。
- 81 ≥ 栈顶值 0：它当左端点不如栈顶(栈顶更靠左、值还不比它大)，跳过不入栈。
- 99 ≥ 栈顶值 0：它当左端点不如栈顶(栈顶更靠左、值还不比它大)，跳过不入栈。
- 104 ≥ 栈顶值 0：它当左端点不如栈顶(栈顶更靠左、值还不比它大)，跳过不入栈。
- 110 ≥ 栈顶值 0：它当左端点不如栈顶(栈顶更靠左、值还不比它大)，跳过不入栈。
- 124 ≥ 栈顶值 0：它当左端点不如栈顶(栈顶更靠左、值还不比它大)，跳过不入栈。
- 131 ≥ 栈顶值 0：它当左端点不如栈顶(栈顶更靠左、值还不比它大)，跳过不入栈。
- 14第一步完成。蓝色这些下标是全部「候选左端点」，它们的值严格递减。接下来 j 从最右端往左走，逐个尝试配坡。
- 15j 来到下标 9(值 1)。从栈顶开始看：栈顶下标的值若 ≤ 1 就能配成坡。
- 16栈顶下标 3(值 0) ≤ 1，配成一个坡，宽度 9−3=6(绿色)。比之前更宽，刷新最大宽度为 6。弹出栈顶(它再往左的 j 只会更窄)，继续看新栈顶。
- 17栈顶下标 2(值 1) ≤ 1，配成一个坡，宽度 9−2=7(绿色)。比之前更宽，刷新最大宽度为 7。弹出栈顶(它再往左的 j 只会更窄)，继续看新栈顶。
- 18现在栈顶值 8 比 1 大，配不成坡(需要左端点 ≤ 右端点)。j 继续往左走。
- 19j 来到下标 8(值 4)。从栈顶开始看：栈顶下标的值若 ≤ 4 就能配成坡。
- 20现在栈顶值 8 比 4 大，配不成坡(需要左端点 ≤ 右端点)。j 继续往左走。
- 21j 来到下标 7(值 0)。从栈顶开始看：栈顶下标的值若 ≤ 0 就能配成坡。
- 22现在栈顶值 8 比 0 大，配不成坡(需要左端点 ≤ 右端点)。j 继续往左走。
- 23j 来到下标 6(值 4)。从栈顶开始看：栈顶下标的值若 ≤ 4 就能配成坡。
- 24现在栈顶值 8 比 4 大，配不成坡(需要左端点 ≤ 右端点)。j 继续往左走。
- 25j 来到下标 5(值 9)。从栈顶开始看：栈顶下标的值若 ≤ 9 就能配成坡。
- 26栈顶下标 1(值 8) ≤ 9，配成一个坡，宽度 5−1=4(绿色)。没超过已知最大 7。弹出栈顶(它再往左的 j 只会更窄)，继续看新栈顶。
- 27栈顶下标 0(值 9) ≤ 9，配成一个坡，宽度 5−0=5(绿色)。没超过已知最大 7。弹出栈顶(它再往左的 j 只会更窄)，继续看新栈顶。
- 28候选栈已经空了，说明每个候选左端点都找到了它能配的最靠右的 j。可以收工，最大宽度 7。
- 29最宽的坡是绿色这一段:左端 i=2(值 1)、右端 j=9(值 1)，满足 1 ≤ 1，宽度 7。这就是答案。
⚠️ 容易写错的地方
✗ 错：入栈时用 ≤ 比较
✓ 对：只在 nums[i] 严格小于栈顶才入栈
相等的左端点下标更大、不会更优,入栈是多余
✗ 错：从左往右扫 j 配坡
✓ 对：必须从右往左扫 j
从右扫保证第一次配上栈顶就是该左端点能达到的最宽,弹出后不漏
✗ 错：弹栈条件用 < 而非 ≤
✓ 对：坡允许相等(nums[i] ≤ nums[j]),用 ≤
题目定义 ≤,用 < 会漏掉相等的坡
完整代码（Python / C++ / Java）
Python
from typing import List
class Solution:
def maxWidthRamp(self, nums: List[int]) -> int:
stack = []
for i, x in enumerate(nums):
if not stack or x < nums[stack[-1]]:
stack.append(i)
ans = 0
for j in range(len(nums) - 1, -1, -1):
while stack and nums[stack[-1]] <= nums[j]:
ans = max(ans, j - stack.pop())
return ansC++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int maxWidthRamp(vector<int>& nums) {
vector<int> st;
for (int i = 0; i < (int)nums.size(); ++i) {
if (st.empty() || nums[i] < nums[st.back()]) st.push_back(i);
}
int ans = 0;
for (int j = nums.size() - 1; j >= 0; --j) {
while (!st.empty() && nums[st.back()] <= nums[j]) {
ans = max(ans, j - st.back());
st.pop_back();
}
}
return ans;
}
};Java
import java.util.*;
class Solution {
public int maxWidthRamp(int[] nums) {
Deque<Integer> stack = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++) {
if (stack.isEmpty() || nums[i] < nums[stack.peek()]) stack.push(i);
}
int ans = 0;
for (int j = nums.length - 1; j >= 0; j--) {
while (!stack.isEmpty() && nums[stack.peek()] <= nums[j]) {
ans = Math.max(ans, j - stack.pop());
}
}
return ans;
}
}复杂度
时间
O(n)
建栈一趟 + 右扫一趟,每个下标至多入栈/出栈一次
空间
O(n)
候选下标栈最多 n 个
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 最大宽度坡 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
为什么不用对每个 j 二分找最左的可行 i?+
可以:把「前缀最小值」数组或对候选栈二分也能做到 O(n log n)。但单调栈 + 右扫是 O(n),更优且不需要额外有序结构,所以是首选解法。
候选栈里的值为什么一定严格递减?+
因为我们只在 nums[i] 严格小于当前栈顶时才入栈,所以从栈底到栈顶下标递增、值严格递减。这保证右扫弹栈时,一旦栈顶配不上当前 j,更下面的(值更大的)也一定配不上,可以安全停。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 最大宽度坡 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。