罗罗编程学习记录
本页内容 展开查看

02.3.2.2 单调栈与柱状图、接雨水

所属:全栈开发面试题库 / 02 数据结构与算法 / 02.3 链表、栈与队列 / 02.3.2 栈与队列、单调栈

02.3.2.2-001 单调栈的核心思想是什么?

一句话结论

栈内元素保持单调递增或递减;新元素入栈前,弹出所有破坏单调性的栈顶元素,弹栈时结算该元素对应的最近更大/更小关系;每个元素入栈出栈各一次,O(n)。

概念解释

  • 单调方向:递增栈找更小,递减栈找更大。
  • 弹栈即结算:被弹出元素的答案由当前元素给出。
  • 存索引便于计算距离宽度。

原理流程

  1. 遍历元素。
  2. 比较栈顶与当前,破坏单调则弹栈结算。
  3. 当前元素入栈。

代码 / 图示

递减栈(找右侧更大):
栈顶 ≥ 次栈顶
当前更大 → 弹栈,当前是栈顶右侧第一个更大

常见误区

  • 误区:先入栈再排序维护;正解:入栈前即时弹栈。
  • 误区:单调栈处理任意顺序问题;正解:针对最近更大/更小类。

追问

  • Q:单调栈复杂度? A:O(n),每元素一次入栈一次出栈。
  • Q:栈存值还是索引? A:距离/宽度题存索引。

02.3.2.2-002 每日温度(LC 739)怎么做?

一句话结论

递减单调栈存温度下标;当前温度高于栈顶下标温度时,弹栈并记录天数差;O(n) 时间 O(n) 空间。

概念解释

  • 答案:右侧第一个更暖的天数。
  • 栈存待求答案的下标。
  • 升温即结算。

原理流程

  1. 遍历 i。
  2. 当前温度 > 栈顶温度,弹栈算 i - idx。
  3. 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) 空间。

概念解释

  • 哈希:元素 → 右侧更大值。
  • 单调栈预计算。
  • 小规模查询查表。

原理流程

  1. 扫 nums2,弹栈时记录映射。
  2. 无更大记 -1。
  3. 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) 空间。

概念解释

  • 环形:尾部接回头部。
  • 双倍遍历模拟绕圈。
  • 第二轮只为已入栈元素找答案。

原理流程

  1. for i 从 0 到 2n-1。
  2. 取 arr[i % n] 比较弹栈。
  3. 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()] 比较。

概念解释

  • 位置量:下标差。
  • 重复值:索引唯一。
  • 取值:数组回查。

原理流程

  1. 栈压下标。
  2. 比较时取数组值。
  3. 结算用下标差。

代码 / 图示

栈:[2, 5](下标)
比较:arr[5] > arr[2]
宽度:当前下标 - 栈顶下标

常见误区

  • 误区:存值后算宽度;正解:值无法反推位置。
  • 误区:重复值用值作键;正解:索引区分。

追问

  • Q:什么题可以存值? A:只需值匹配、不涉及位置差时。
  • Q:索引栈越界? A:只压合法下标。

02.3.2.2-006 递增栈与递减栈怎么选?

一句话结论

找右侧更大用递减栈(栈内从底到顶递减);找右侧更小用递增栈;方向由答案指向的比较关系决定,先明确“更大还是更小”再选栈。

概念解释

  • 递减栈:新元素更大时弹栈。
  • 递增栈:新元素更小时弹栈。
  • 两侧需求可分别跑两遍。

原理流程

  1. 定义目标:更大/更小。
  2. 选对应单调方向。
  3. 弹栈条件反向。

代码 / 图示

更大 → 递减栈
更小 → 递增栈

常见误区

  • 误区:两种方向混用不说明;正解:题目标明单调方向。
  • 误区:栈内顺序从顶到底记反;正解:先画图确认。

追问

  • Q:同时要左右更大? A:两遍单调栈,分别向左向右。
  • Q:相等元素弹不弹? A:按“严格/非严格”口径,相同值通常不弹。

02.3.2.2-007 柱状图中最大矩形(LC 84)怎么做?

一句话结论

递增单调栈存柱子下标;当前柱高低于栈顶时弹出栈顶,以该柱高为矩形高,宽度为当前下标到新栈顶下标之差;O(n) 时间 O(n) 空间。

概念解释

  • 矩形高:被弹柱子高度。
  • 宽度:左右边界之间。
  • 递增栈保证栈顶左侧更矮。

原理流程

  1. 柱子下标入递增栈。
  2. 当前更矮则弹栈算面积。
  3. 末尾补高度 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(左右墙) - 底高。

原理流程

  1. 下标入递减栈。
  2. 当前更高则弹栈。
  3. 左墙为新栈顶,右墙为当前,算一层水量。

代码 / 示例

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) 空间。

概念解释

  • 短板决定水位。
  • 矮侧移动即可确定水量。
  • 无需数组存前缀最大值。

原理流程

  1. 左右最大初值 0。
  2. 比较左右高度,矮侧计算并移动。
  3. 更新对应最大高度。

代码 / 示例

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) 空间,思路直观。

概念解释

  • 前缀最大:向左最高。
  • 后缀最大:向右最高。
  • 逐柱累加。

原理流程

  1. 左向右扫填 leftMax。
  2. 右向左扫填 rightMax。
  3. 逐柱算水量求和。

代码 / 示例

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 单调栈结算时,当前元素扮演什么角色?

一句话结论

当前元素是被弹元素右侧第一个满足比较关系的边界;弹栈时答案由当前元素与新栈顶(左侧边界)共同确定;当前元素之后才入栈成为新待结算元素。

概念解释

  • 右边界:当前下标。
  • 左边界:弹后栈顶。
  • 结算:被弹元素定案。

原理流程

  1. 当前比较触发弹栈。
  2. 记录左右边界。
  3. 当前入栈等待未来结算。

代码 / 图示

[左边界] 被弹 [当前右边界]
接雨水:高度取两侧矮
柱状图:宽度为左右间距

常见误区

  • 误区:当前元素先入栈再结算;正解:先弹栈结算,再入栈。
  • 误区:左边界被弹后丢失;正解:弹一次后新栈顶即左边界。

追问

  • Q:栈空时左边界是谁? A:虚拟边界 -1 或 0 哨兵。
  • Q:当前元素相等弹不弹? A:按严格/非严格口径。

02.3.2.2-012 柱状图最大矩形的宽度怎么算?

一句话结论

弹出高度 h 的柱 i,左边界为弹后栈顶下标 L(无则 -1),右边界为当前下标 R;宽度 R - L - 1,面积 h × 宽度。

概念解释

  • 左右边界:最近更矮柱。
  • 中间均可作为 h 的基底。
  • 减 1:排除边界柱本身。

原理流程

  1. 弹栈取柱高与下标。
  2. 新栈顶为左边界。
  3. 宽度与面积计算。

代码 / 图示

L(更矮) … i … R(更矮)
宽度 = R - L - 1

常见误区

  • 误区:宽度 R - L;正解:边界柱不计入。
  • 误区:左边界用被弹前栈顶;正解:被弹后新栈顶。

追问

  • Q:左边界不存在? A:L = -1。
  • Q:右边界不存在? A:末尾哨兵 0 作为 R。

02.3.2.2-013 接雨水按层蓄水与按柱蓄水有什么区别?

一句话结论

单调栈按横向凹段逐层结算;DP/双指针按纵向每根柱子上方水量累加;总量相同,视角不同;单调栈逐层处理凹坑。

概念解释

  • 按层:横向段。
  • 按柱:纵向柱上水量。
  • 等价:体积守恒。

原理流程

  1. 单调栈遇右墙弹层。
  2. DP 逐柱求上下水位。
  3. 总和一致。

代码 / 图示

按柱:每根柱头顶到水位的体积
按层:每个凹坑逐层宽度 × 层高

常见误区

  • 误区:两种算法结果不同;正解:总量一致。
  • 误区:单调栈一次算整坑高度;正解:逐层弹栈累加。

追问

  • Q:哪种好解释? A:DP 按柱直观;双指针空间最优。
  • Q:地形平顶? A:等高层逐层结算仍正确。

02.3.2.2-014 循环数组单调栈怎么处理边界?

一句话结论

复制一份数组或遍历 2n 次取模;第二轮只为第一轮入栈元素补右侧答案;答案初始化 -1,避免绕一圈仍无更大。

概念解释

  • 环形:首尾相连。
  • 双倍扫描。
  • 答案默认 -1。

原理流程

  1. 遍历 2n,下标取模。
  2. 第一轮入栈。
  3. 弹栈结算,未结算保持 -1。

代码 / 图示

i ∈ [0, 2n),idx = i % n

常见误区

  • 误区:复制数组后索引混淆;正解:取模或双份长度统一口径。
  • 误区:第二轮再入栈;正解:重复入栈导致错误结算。

追问

  • Q:绕一圈还没更大? A:答案 -1。
  • Q:环形找更小同理? A:栈方向反转即可。

02.3.2.2-015 单调栈能求左侧更小元素吗?

一句话结论

可以,从左向右遍历用递增栈记录右侧关系,或从右向左遍历求左侧关系;方向与遍历方向配合;左右答案可分别计算。

概念解释

  • 向右:左→右扫描。
  • 向左:右→左扫描。
  • 同方向栈结构复用。

原理流程

  1. 确定答案指向左侧还是右侧。
  2. 选扫描方向。
  3. 栈内单调方向对应。

代码 / 图示

右侧更大:左→右,递减栈
左侧更大:右→左,递减栈

常见误区

  • 误区:求左侧答案也从左扫;正解:按边界方向选择扫描顺序。
  • 误区:左右答案混在同一栈;正解:两遍分别维护。

追问

  • Q:同时求左右更大? A:两遍单调栈,存两组答案。
  • Q:边界元素无左侧? A:记 -1 或约定值。

02.3.2.2-016 单调栈题有哪些边界用例?

一句话结论

空数组、单元素、全递增、全递减、全相同值、双峰地形、平顶宽段;验证哨兵补零、相等不弹、栈空 break 与默认答案。

概念解释

  • 空与最短。
  • 单调极端。
  • 相等与平顶。

原理流程

  1. 空数组直接返回。
  2. 构造递增/递减/全同。
  3. 检查结算宽度与水量。

代码 / 图示

[] / [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。

概念解释

  • 栈:后入先出,找边界。
  • 队列:窗口进出两端。
  • 用途不同。

原理流程

  1. 栈:弹栈结算边界。
  2. 队列:队尾维护单调,队首删过期。
  3. 按窗口/边界题型选型。

代码 / 图示

单调栈:下一个更大
单调队列:窗口最大

常见误区

  • 误区:两者可互换;正解:操作端与场景不同。
  • 误区:队列也只从一端操作;正解:双端维护。

追问

  • Q:窗口最大用栈行不行? A:栈不支持按位置淘汰队首,不合适。
  • Q:两者复杂度? A:均 O(n),元素至多入队/栈出一次。

02.3.2.2-018 为什么接雨水双指针不需要额外数组?

一句话结论

矮侧指针移动时,该侧水位已由对侧较高墙保证:只要对侧墙更高,本侧积水上限就是本侧最大高度;因此只维护左右两个最大即可。

概念解释

  • 短板:较矮一侧。
  • 水位:本侧最大与当前差。
  • 两侧最大滚动更新。

原理流程

  1. 比较左右指针高度。
  2. 矮侧移动并按本侧最大算水。
  3. 高侧等待。

代码 / 图示

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。
  • 元素状态:在栈内或已结算。
  • 总操作线性。

原理流程

  1. 统计 push 次数 ≤ n。
  2. pop 次数 ≤ push 次数。
  3. 合计 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)。

概念解释

  • 线性扫描:每元素常数次操作。
  • 空间:栈/前缀数组/双指针变量。
  • 口径:最坏与平均一致。

原理流程

  1. 标注扫描轮次。
  2. 标注辅助结构规模。
  3. 按方法分列空间。

代码 / 图示

每日温度: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/双指针复杂度。