02.3.2.2 单调栈与柱状图、接雨水
所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈
02.3.2.2-001 单调栈的核心思想是什么?
一句话结论
栈内元素保持单调递增或递减;新元素入栈前,弹出所有破坏单调性的栈顶元素,弹栈时结算该元素对应的最近更大/更小关系;每个元素入栈出栈各一次,O(n)。
概念解释
- 单调方向:递增栈找更小,递减栈找更大。
- 弹栈即结算:被弹出元素的答案由当前元素给出。
- 存索引便于计算距离宽度。
原理流程
- 遍历元素。
- 比较栈顶与当前,破坏单调则弹栈结算。
- 当前元素入栈。
代码 / 图示
递减栈(找右侧更大):
栈顶 ≥ 次栈顶
当前更大 → 弹栈,当前是栈顶右侧第一个更大
常见误区
- 误区:先入栈再排序维护;正解:入栈前即时弹栈。
- 误区:单调栈处理任意顺序问题;正解:针对最近更大/更小类。
追问
- Q:单调栈复杂度? A:O(n),每元素一次入栈一次出栈。
- Q:栈存值还是索引? A:距离/宽度题存索引。
02.3.2.2-002 每日温度(LC 739)怎么做?
一句话结论
递减单调栈存温度下标;当前温度高于栈顶下标温度时,弹栈并记录天数差;O(n) 时间 O(n) 空间。
概念解释
- 答案:右侧第一个更暖的天数。
- 栈存待求答案的下标。
- 升温即结算。
原理流程
- 遍历 i。
- 当前温度 > 栈顶温度,弹栈算 i - idx。
- i 入栈。
代码 / 示例
public int[] dailyTemperatures(int[] t) {
int[] ans = new int[t.length];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < t.length; i++) {
while (!st.isEmpty() && t[i] > t[st.peek()]) {
int idx = st.pop();
ans[idx] = i - idx;
}
st.push(i);
}
return ans;
}
常见误区
- 误区:温度相等也弹栈;正解:严格更大才弹,相等继续等。
- 误区:栈存温度值;正解:存下标算天数差。
追问
- Q:末尾未升温? A:ans 保持 0。
- Q:暴力法对照? A:双层扫描 O(n²)。
02.3.2.2-003 下一个更大元素 I(LC 496)怎么做?
一句话结论
对 nums2 用递减单调栈预计算每个元素右侧更大值哈希表,再查 nums1 得到答案;O(m+n) 时间 O(n) 空间。
概念解释
- 哈希:元素 → 右侧更大值。
- 单调栈预计算。
- 小规模查询查表。
原理流程
- 扫 nums2,弹栈时记录映射。
- 无更大记 -1。
- nums1 逐值查表。
代码 / 示例
public int[] nextGreaterElement(int[] nums1, int[] nums2) {
Map<Integer, Integer> map = new HashMap<>();
Deque<Integer> st = new ArrayDeque<>();
for (int x : nums2) {
while (!st.isEmpty() && x > st.peek()) map.put(st.pop(), x);
st.push(x);
}
int[] ans = new int[nums1.length];
for (int i = 0; i < nums1.length; i++) ans[i] = map.getOrDefault(nums1[i], -1);
return ans;
}
常见误区
- 误区:栈存索引而元素可重复;正解:本题值唯一,存值可用,重复场景存索引。
- 误区:未命中查不到默认 0;正解:默认 -1。
追问
- Q:元素重复怎么办? A:存索引,避免键冲突。
- Q:找更小元素? A:栈方向反过来,递增栈。
02.3.2.2-004 下一个更大元素 II 循环数组(LC 503)怎么做?
一句话结论
数组长度 n,遍历 2n 次,下标 i % n;环形下绕一圈找右侧更大;O(n) 时间 O(n) 空间。
概念解释
- 环形:尾部接回头部。
- 双倍遍历模拟绕圈。
- 第二轮只为已入栈元素找答案。
原理流程
- for i 从 0 到 2n-1。
- 取
arr[i % n]比较弹栈。 - i < n 时入栈。
代码 / 示例
public int[] nextGreaterElements(int[] nums) {
int n = nums.length;
int[] ans = new int[n];
Arrays.fill(ans, -1);
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < 2 * n; i++) {
int idx = i % n;
while (!st.isEmpty() && nums[idx] > nums[st.peek()]) {
ans[st.pop()] = nums[idx];
}
if (i < n) st.push(idx);
}
return ans;
}
常见误区
- 误区:第二轮也重复入栈;正解:只第一轮入栈。
- 误区:取模下标错误;正解:
i % n。
追问
- Q:全相同值? A:ans 全 -1。
- Q:绕一圈最多比较几次? A:每元素栈内处理常数次。
02.3.2.2-005 单调栈为什么通常存索引而不是值?
一句话结论
答案常与位置相关(天数差、宽度、距离),索引可回取原数组值并计算跨度;存值丢失位置信息,重复值也无法区分;结算时用 arr[stack.peek()] 比较。
概念解释
- 位置量:下标差。
- 重复值:索引唯一。
- 取值:数组回查。
原理流程
- 栈压下标。
- 比较时取数组值。
- 结算用下标差。
代码 / 图示
栈:[2, 5](下标)
比较:arr[5] > arr[2]
宽度:当前下标 - 栈顶下标
常见误区
- 误区:存值后算宽度;正解:值无法反推位置。
- 误区:重复值用值作键;正解:索引区分。
追问
- Q:什么题可以存值? A:只需值匹配、不涉及位置差时。
- Q:索引栈越界? A:只压合法下标。
02.3.2.2-006 递增栈与递减栈怎么选?
一句话结论
找右侧更大用递减栈(栈内从底到顶递减);找右侧更小用递增栈;方向由答案指向的比较关系决定,先明确“更大还是更小”再选栈。
概念解释
- 递减栈:新元素更大时弹栈。
- 递增栈:新元素更小时弹栈。
- 两侧需求可分别跑两遍。
原理流程
- 定义目标:更大/更小。
- 选对应单调方向。
- 弹栈条件反向。
代码 / 图示
更大 → 递减栈
更小 → 递增栈
常见误区
- 误区:两种方向混用不说明;正解:题目标明单调方向。
- 误区:栈内顺序从顶到底记反;正解:先画图确认。
追问
- Q:同时要左右更大? A:两遍单调栈,分别向左向右。
- Q:相等元素弹不弹? A:按“严格/非严格”口径,相同值通常不弹。
02.3.2.2-007 柱状图中最大矩形(LC 84)怎么做?
一句话结论
递增单调栈存柱子下标;当前柱高低于栈顶时弹出栈顶,以该柱高为矩形高,宽度为当前下标到新栈顶下标之差;O(n) 时间 O(n) 空间。
概念解释
- 矩形高:被弹柱子高度。
- 宽度:左右边界之间。
- 递增栈保证栈顶左侧更矮。
原理流程
- 柱子下标入递增栈。
- 当前更矮则弹栈算面积。
- 末尾补高度 0 哨兵清空栈。
代码 / 示例
public int largestRectangleArea(int[] heights) {
Deque<Integer> st = new ArrayDeque<>();
int max = 0, n = heights.length;
for (int i = 0; i <= n; i++) {
int h = i == n ? 0 : heights[i];
while (!st.isEmpty() && h < heights[st.peek()]) {
int height = heights[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
max = Math.max(max, height * (i - left - 1));
}
st.push(i);
}
return max;
}
常见误区
- 误区:宽度算成 i - 栈顶;正解:弹出后新栈顶为左边界,宽度
i - left - 1。 - 误区:末尾不补哨兵;正解:矮哨兵清空剩余递增柱。
追问
- Q:左右边界是谁? A:最近更矮柱;无边界用 -1 / n。
- Q:暴力法? A:枚举左右边界求最低柱,O(n²)。
02.3.2.2-008 接雨水(LC 42)单调栈法怎么做?
一句话结论
递减单调栈存下标;当前柱高于栈顶时弹出栈底蓄水层:宽度为当前与新栈顶距离,高度为两侧较矮减被弹柱高;逐层累加;O(n) 时间 O(n) 空间。
概念解释
- 栈内递减:待蓄水凹段。
- 弹栈:形成一层水。
- 高度:min(左右墙) - 底高。
原理流程
- 下标入递减栈。
- 当前更高则弹栈。
- 左墙为新栈顶,右墙为当前,算一层水量。
代码 / 示例
public int trap(int[] height) {
Deque<Integer> st = new ArrayDeque<>();
int water = 0;
for (int i = 0; i < height.length; i++) {
while (!st.isEmpty() && height[i] > height[st.peek()]) {
int bottom = st.pop();
if (st.isEmpty()) break;
int left = st.peek();
int h = Math.min(height[left], height[i]) - height[bottom];
water += h * (i - left - 1);
}
st.push(i);
}
return water;
}
常见误区
- 误区:弹栈后栈空仍算水;正解:无左墙 break。
- 误区:水高取较高侧;正解:取较矮侧,短板决定水位。
追问
- Q:底部等高怎么叠加? A:多层弹栈逐层累加。
- Q:单调栈法按什么方向蓄水? A:按横向层段。
02.3.2.2-009 接雨水双指针法是什么思路?
一句话结论
左右指针相向移动,维护左右最大高度;较矮一侧指针移动,该侧可存水量为 maxLeft/Right - 当前高度;O(n) 时间 O(1) 空间。
概念解释
- 短板决定水位。
- 矮侧移动即可确定水量。
- 无需数组存前缀最大值。
原理流程
- 左右最大初值 0。
- 比较左右高度,矮侧计算并移动。
- 更新对应最大高度。
代码 / 示例
public int trap(int[] height) {
int l = 0, r = height.length - 1, leftMax = 0, rightMax = 0, water = 0;
while (l < r) {
if (height[l] < height[r]) {
if (height[l] >= leftMax) leftMax = height[l];
else water += leftMax - height[l];
l++;
} else {
if (height[r] >= rightMax) rightMax = height[r];
else water += rightMax - height[r];
r--;
}
}
return water;
}
常见误区
- 误区:两侧都用同一个最大;正解:左右最大分别维护。
- 误区:高侧先移动;正解:矮侧水位已由对侧更高保证。
追问
- Q:为什么矮侧可以先算? A:对侧更高,水位由本侧最大决定。
- Q:空间 O(1) 怎么来的? A:只存两个最大与指针。
02.3.2.2-010 接雨水动态规划法是什么思路?
一句话结论
预计算每个位置左侧最大高度数组与右侧最大高度数组,逐位置水量 min(leftMax[i], rightMax[i]) - height[i];O(n) 时间 O(n) 空间,思路直观。
概念解释
- 前缀最大:向左最高。
- 后缀最大:向右最高。
- 逐柱累加。
原理流程
- 左向右扫填 leftMax。
- 右向左扫填 rightMax。
- 逐柱算水量求和。
代码 / 示例
int n = height.length;
int[] left = new int[n], right = new int[n];
left[0] = height[0];
for (int i = 1; i < n; i++) left[i] = Math.max(left[i - 1], height[i]);
right[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; i--) right[i] = Math.max(right[i + 1], height[i]);
int water = 0;
for (int i = 0; i < n; i++) water += Math.min(left[i], right[i]) - height[i];
常见误区
- 误区:最大含当前柱;正解:含当前柱也可,差值自然非负。
- 误区:水量取最大侧;正解:取较矮侧。
追问
- Q:三种方法复杂度? A:都 O(n),空间 DP O(n)、栈 O(n)、双指针 O(1)。
- Q:哪种最直观? A:DP 思路直接,双指针空间最优。
02.3.2.2-011 单调栈结算时,当前元素扮演什么角色?
一句话结论
当前元素是被弹元素右侧第一个满足比较关系的边界;弹栈时答案由当前元素与新栈顶(左侧边界)共同确定;当前元素之后才入栈成为新待结算元素。
概念解释
- 右边界:当前下标。
- 左边界:弹后栈顶。
- 结算:被弹元素定案。
原理流程
- 当前比较触发弹栈。
- 记录左右边界。
- 当前入栈等待未来结算。
代码 / 图示
[左边界] 被弹 [当前右边界]
接雨水:高度取两侧矮
柱状图:宽度为左右间距
常见误区
- 误区:当前元素先入栈再结算;正解:先弹栈结算,再入栈。
- 误区:左边界被弹后丢失;正解:弹一次后新栈顶即左边界。
追问
- Q:栈空时左边界是谁? A:虚拟边界 -1 或 0 哨兵。
- Q:当前元素相等弹不弹? A:按严格/非严格口径。
02.3.2.2-012 柱状图最大矩形的宽度怎么算?
一句话结论
弹出高度 h 的柱 i,左边界为弹后栈顶下标 L(无则 -1),右边界为当前下标 R;宽度 R - L - 1,面积 h × 宽度。
概念解释
- 左右边界:最近更矮柱。
- 中间均可作为 h 的基底。
- 减 1:排除边界柱本身。
原理流程
- 弹栈取柱高与下标。
- 新栈顶为左边界。
- 宽度与面积计算。
代码 / 图示
L(更矮) … i … R(更矮)
宽度 = R - L - 1
常见误区
- 误区:宽度 R - L;正解:边界柱不计入。
- 误区:左边界用被弹前栈顶;正解:被弹后新栈顶。
追问
- Q:左边界不存在? A:L = -1。
- Q:右边界不存在? A:末尾哨兵 0 作为 R。
02.3.2.2-013 接雨水按层蓄水与按柱蓄水有什么区别?
一句话结论
单调栈按横向凹段逐层结算;DP/双指针按纵向每根柱子上方水量累加;总量相同,视角不同;单调栈逐层处理凹坑。
概念解释
- 按层:横向段。
- 按柱:纵向柱上水量。
- 等价:体积守恒。
原理流程
- 单调栈遇右墙弹层。
- DP 逐柱求上下水位。
- 总和一致。
代码 / 图示
按柱:每根柱头顶到水位的体积
按层:每个凹坑逐层宽度 × 层高
常见误区
- 误区:两种算法结果不同;正解:总量一致。
- 误区:单调栈一次算整坑高度;正解:逐层弹栈累加。
追问
- Q:哪种好解释? A:DP 按柱直观;双指针空间最优。
- Q:地形平顶? A:等高层逐层结算仍正确。
02.3.2.2-014 循环数组单调栈怎么处理边界?
一句话结论
复制一份数组或遍历 2n 次取模;第二轮只为第一轮入栈元素补右侧答案;答案初始化 -1,避免绕一圈仍无更大。
概念解释
- 环形:首尾相连。
- 双倍扫描。
- 答案默认 -1。
原理流程
- 遍历 2n,下标取模。
- 第一轮入栈。
- 弹栈结算,未结算保持 -1。
代码 / 图示
i ∈ [0, 2n),idx = i % n
常见误区
- 误区:复制数组后索引混淆;正解:取模或双份长度统一口径。
- 误区:第二轮再入栈;正解:重复入栈导致错误结算。
追问
- Q:绕一圈还没更大? A:答案 -1。
- Q:环形找更小同理? A:栈方向反转即可。
02.3.2.2-015 单调栈能求左侧更小元素吗?
一句话结论
可以,从左向右遍历用递增栈记录右侧关系,或从右向左遍历求左侧关系;方向与遍历方向配合;左右答案可分别计算。
概念解释
- 向右:左→右扫描。
- 向左:右→左扫描。
- 同方向栈结构复用。
原理流程
- 确定答案指向左侧还是右侧。
- 选扫描方向。
- 栈内单调方向对应。
代码 / 图示
右侧更大:左→右,递减栈
左侧更大:右→左,递减栈
常见误区
- 误区:求左侧答案也从左扫;正解:按边界方向选择扫描顺序。
- 误区:左右答案混在同一栈;正解:两遍分别维护。
追问
- Q:同时求左右更大? A:两遍单调栈,存两组答案。
- Q:边界元素无左侧? A:记 -1 或约定值。
02.3.2.2-016 单调栈题有哪些边界用例?
一句话结论
空数组、单元素、全递增、全递减、全相同值、双峰地形、平顶宽段;验证哨兵补零、相等不弹、栈空 break 与默认答案。
概念解释
- 空与最短。
- 单调极端。
- 相等与平顶。
原理流程
- 空数组直接返回。
- 构造递增/递减/全同。
- 检查结算宽度与水量。
代码 / 图示
[] / [1]
1 2 3 4
4 3 2 1
2 2 2
常见误区
- 误区:全相同值弹栈;正解:严格比较才弹,相等等待。
- 误区:单元素面积/水量为 0;正解:正确口径为 0。
追问
- Q:两个等高柱间蓄水? A:无更低底部,水量 0。
- Q:柱状图单柱面积? A:高度 × 1。
02.3.2.2-017 单调栈与单调队列有什么区别?
一句话结论
单调栈是 LIFO 结构,处理最近更大/更小与跨度;单调队列是双端队列,处理滑动窗口内最大/最小值,队尾维护单调、队首弹出过期;见 02.3.2.4。
概念解释
- 栈:后入先出,找边界。
- 队列:窗口进出两端。
- 用途不同。
原理流程
- 栈:弹栈结算边界。
- 队列:队尾维护单调,队首删过期。
- 按窗口/边界题型选型。
代码 / 图示
单调栈:下一个更大
单调队列:窗口最大
常见误区
- 误区:两者可互换;正解:操作端与场景不同。
- 误区:队列也只从一端操作;正解:双端维护。
追问
- Q:窗口最大用栈行不行? A:栈不支持按位置淘汰队首,不合适。
- Q:两者复杂度? A:均 O(n),元素至多入队/栈出一次。
02.3.2.2-018 为什么接雨水双指针不需要额外数组?
一句话结论
矮侧指针移动时,该侧水位已由对侧较高墙保证:只要对侧墙更高,本侧积水上限就是本侧最大高度;因此只维护左右两个最大即可。
概念解释
- 短板:较矮一侧。
- 水位:本侧最大与当前差。
- 两侧最大滚动更新。
原理流程
- 比较左右指针高度。
- 矮侧移动并按本侧最大算水。
- 高侧等待。
代码 / 图示
height[l] < height[r] → l 侧水位 ≤ leftMax
常见误区
- 误区:必须预知两侧最大数组;正解:指针移动时滚动维护。
- 误区:高侧先移动会漏算;正解:矮侧先算水位确定。
追问
- Q:相等高度移动哪侧? A:代码移动一侧均可,水量口径一致。
- Q:O(1) 空间代价? A:算法理解要求高,思路不如 DP 直观。
02.3.2.2-019 单调栈的“每个元素只入栈出栈一次”怎么理解?
一句话结论
循环看似嵌套 while,但每个元素最多被 push 一次、pop 一次;总弹栈次数 ≤ n,整体 O(n),不是 O(n²)。
概念解释
- 均摊:外层 n 次,内层累计 ≤ n。
- 元素状态:在栈内或已结算。
- 总操作线性。
原理流程
- 统计 push 次数 ≤ n。
- pop 次数 ≤ push 次数。
- 合计 O(n)。
代码 / 图示
外层 n 轮
内层 while 总弹出 ≤ n
常见误区
- 误区:while 嵌套就是 O(n²);正解:按元素出入栈计数均摊。
- 误区:同一元素多次弹栈;正解:弹出后不再回栈。
追问
- Q:什么情况会退化? A:单调栈每个元素仍一次入出,不退化。
- Q:均摊分析适用哪些结构? A:动态数组扩容、单调栈出入栈。
02.3.2.2-020 本知识域复杂度怎么汇报?
一句话结论
单调栈系列 O(n) 时间 O(n) 栈空间;柱状图最大矩形 O(n)/O(n);接雨水 DP O(n)/O(n)、单调栈 O(n)/O(n)、双指针 O(n)/O(1);循环数组遍历 2n 仍 O(n)。
概念解释
- 线性扫描:每元素常数次操作。
- 空间:栈/前缀数组/双指针变量。
- 口径:最坏与平均一致。
原理流程
- 标注扫描轮次。
- 标注辅助结构规模。
- 按方法分列空间。
代码 / 图示
每日温度:O(n) / O(n)
柱状图:O(n) / O(n)
接雨水双指针:O(n) / O(1)
常见误区
- 误区:单调栈 O(n²);正解:均摊 O(n)。
- 误区:接雨水双指针 O(n) 空间;正解:O(1)。
追问
- Q:哪些题必须 O(n) 空间? A:需记录左右边界且无法滚动时。
- Q:面试先讲哪种方法? A:先给单调栈模板,再对照 DP/双指针复杂度。