GU𝐆𝐫𝐨𝐰 𝐔𝐩
返回文章列表
数据结构与算法
算法单调栈

每日温度、下一个更大元素与接雨水

上一篇建立了单调栈的模型：栈存下标、弹栈即结算、均摊 O(n)。这篇用五道题把模型落到代码，覆盖入门模板、循环数组变式、积水问题三种视角和矩形面积计算。

每日温度（739）：递减栈逐行讲

739. 每日温度：每天记录气温的数组，求"至少等几天才有更高的气温"，等不到则记 0。翻译成单调栈语言：为每个元素找右侧第一个更大元素的位置，答案记为距离。要找"更大"，需要单调递减栈（栈底到栈顶温度递减）：

class Solution {
    public int[] dailyTemperatures(int[] temperatures) {
        int n = temperatures.length;
        int[] result = new int[n];
        Deque<Integer> stack = new ArrayDeque<>(); // 存下标，对应温度单调递减
 
        for (int i = 0; i < n; i++) {
            // 当前温度 > 栈顶温度：栈顶这天的"下一个更暖天"就是 i，结算弹栈
            while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
                int top = stack.pop();
                result[top] = i - top; // 记距离，而不是温度值
            }
            stack.push(i); // 自己还没等到答案，入栈等待
        }
        // 循环结束栈里剩下的都是"等不到更暖天"的，result 默认 0，无需处理
        return result;
    }
}

拿 [73,74,75,71,69,72,76,73] 手工模拟前几步，感受弹栈结算的节奏：

i=0 (73): 栈空 → 入栈           栈: [0]
i=1 (74): 74>73，弹出0记1      栈: [1]
i=2 (75): 75>74，弹出1记1      栈: [2]
i=3 (71): 71<75 → 入栈         栈: [2,3]
i=4 (69): 69<71 → 入栈         栈: [2,3,4]
i=5 (72): 72>69 弹出4记1；72>71 弹出3记2；72<75 停  栈: [2,5]

i=5 一步连弹两个，正是单调栈"一次结算多笔欠账"的效率来源。

下一个更大元素（496/503）：取模技巧

496：主数组跑栈，哈希表查答案

496. 下一个更大元素 I：nums1 是 nums2 的子集，对 nums1 每个元素求其在 nums2 中的下一个更大元素。别对 nums1 逐个元素扫 nums2——只对 nums2 跑一次单调栈，把"元素 → 下一个更大元素"存进 HashMap，nums1 直接查表：

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> nextGreater = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>(); // 存 nums2 的下标
 
        for (int i = 0; i < nums2.length; i++) {
            while (!stack.isEmpty() && nums2[i] > nums2[stack.peek()]) {
                nextGreater.put(nums2[stack.pop()], nums2[i]); // 值 → 答案值
            }
            stack.push(i);
        }
 
        int[] result = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            result[i] = nextGreater.getOrDefault(nums1[i], -1);
        }
        return result;
    }
}

503：循环数组遍历两圈

503. 下一个更大元素 II：数组是环形的，要考虑绕回头部继续找。通用转换：遍历 2n 次、实际下标对 n 取模，逻辑上相当于把数组复制一份接在后面，但不用真的扩容：

class Solution {
    public int[] nextGreaterElements(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
 
        // 遍历两圈：i 从 0 到 2n-1，用 i % n 映射回真实下标
        for (int i = 0; i < 2 * n; i++) {
            int idx = i % n;
            while (!stack.isEmpty() && nums[idx] > nums[stack.peek()]) {
                result[stack.pop()] = nums[idx];
            }
            // 只在第一圈入栈（第二圈重复入栈不影响正确性但浪费操作）
            if (i < n) stack.push(idx);
        }
        return result;
    }
}

为什么取模正确？第一圈给每个元素入栈并尽力结算；第二圈相当于"绕回来看前缀"，让没找到答案的元素有机会被数组头部的更大值结算，两圈后仍无答案的保持 -1。

接雨水（42）：三种解法对比

42. 接雨水：柱子高度数组，求能接多少雨水。核心几何事实：每个位置能接的水 = min(左边最高, 右边最高) - 自己的高度，三种解法都在算这个式子，差别只在"左右最高"怎么获得。

解法一：按列 DP（左右最大值数组）

预计算两个数组：maxLeft[i]（i 左侧含自身的最大高度）、maxRight[i]（右侧含自身），然后逐列累加：

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int[] maxLeft = new int[n], maxRight = new int[n];
        maxLeft[0] = height[0];
        for (int i = 1; i < n; i++) maxLeft[i] = Math.max(maxLeft[i - 1], height[i]);
 
        maxRight[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) maxRight[i] = Math.max(maxRight[i + 1], height[i]);
 
        int water = 0;
        for (int i = 0; i < n; i++) {
            water += Math.min(maxLeft[i], maxRight[i]) - height[i];
        }
        return water;
    }
}

解法二：按行双指针

双指针从两端收拢，维护 leftMax 和 rightMax：哪边的最大值更小，就结算哪边（因为小的一侧的积水由它决定，另一侧必然有更高的墙兜底）：

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int leftMax = 0, rightMax = 0, water = 0;
 
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) {
                water += leftMax - height[left++]; // 左侧更矮的一侧决定积水
            } else {
                water += rightMax - height[right--];
            }
        }
        return water;
    }
}

解法三：单调栈（横向接水）

前两种"按列竖着算"，单调栈"按行横着算"：维护单调递减栈，当前柱比栈顶高时形成凹槽——弹栈结算，槽底是刚弹出的柱子，左边界为新栈顶、右边界为当前柱：

class Solution {
    public int trap(int[] height) {
        Deque<Integer> stack = new ArrayDeque<>();
        int water = 0;
 
        for (int i = 0; i < height.length; i++) {
            // 当前柱更高 → 可能形成凹槽，逐层结算
            while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
                int bottom = stack.pop();        // 凹槽底部
                if (stack.isEmpty()) break;      // 左边没有墙，接不了水
                int left = stack.peek();         // 左边界
                // 横向宽度：左右边界之间（不含边界），纵向高度：两边较矮者减槽底
                int w = i - left - 1;
                int h = Math.min(height[left], height[i]) - height[bottom];
                water += w * h;
            }
            stack.push(i);
        }
        return water;
    }
}

三种解法复杂度对比

注意相等高度时用 > 不弹栈，相等元素留在栈里等真正更高的出现再一起结算，避免同一层水被重复计算。三种实现对比：

解法 时间 空间 视角 要点
按列 DP O(n) O(n) 竖着逐列 预计算左右最大值，最直观
按行双指针 O(n) O(1) 横着逐行 谁的 max 小结算谁
单调栈 O(n) O(n) 横着逐层 凹槽逐层结算，乘宽度

柱状图中最大的矩形（84）：首尾哨兵

84. 柱状图中最大的矩形：柱状图每根柱子宽 1，求能勾勒出的最大矩形面积。

对每根柱子问一句：以它为最矮柱时，矩形能向左右扩展多宽——即找它左右两侧第一个更矮的柱子，这正是单调递减栈的场景。边界痛点：柱子一直递增到末尾时，栈里元素直到遍历结束都得不到结算；哨兵技巧是在首尾各补一根高度 0 的柱子，让所有真实柱子在扫描中必然被弹栈，边界逻辑自然消失：

class Solution {
    public int largestRectangleArea(int[] heights) {
        int n = heights.length;
        // 首尾各补一个高度 0 的哨兵柱：开头防左侧越界，结尾逼所有柱子弹栈
        int[] h = new int[n + 2];
        System.arraycopy(heights, 0, h, 1, n);
 
        Deque<Integer> stack = new ArrayDeque<>(); // 单调递减栈，存下标
        int maxArea = 0;
 
        for (int i = 0; i < h.length; i++) {
            // 遇到更矮的柱子：栈顶柱子的"扩散范围"确定，结算面积
            while (!stack.isEmpty() && h[i] < h[stack.peek()]) {
                int cur = stack.pop();            // 以 cur 为最矮柱
                int left = stack.peek();          // 左侧第一个更矮（哨兵保证存在）
                int width = i - left - 1;         // 左右更矮柱之间
                maxArea = Math.max(maxArea, h[cur] * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

用样例 [2,1,5,6,2,3] 演示。补哨兵后高度序列为 0,2,1,5,6,2,3,0（下标 0~7），当 i=5（值为 2）比栈顶的 6、5 都矮时，触发连续弹栈：

弹 6（下标4）: left=下标3(值5)，宽 = 5-3-1 = 1，面积 = 6×1 = 6
弹 5（下标3）: left=下标2(值1)，宽 = 5-2-1 = 2，面积 = 5×2 = 10 ← 全局最大

弹 5 能得到宽度 2，是因为左边界"越过"了刚弹出的 6——弹栈后新栈顶就是第一个更矮的左边界，中间更高的柱子全被矩形覆盖。两条易错提醒：相等高度时弹栈条件用严格小于 <，等高柱子留在栈里，最终由同批等高柱中最右的那根以完整宽度结算，面积依然正确；宽度要 -1，因为左右边界都是更矮的柱，不参与矩形。

LeetCode 题目清单

参考