LeetCode 面试题 17.21. 直方图的水量

约 11 分钟
文章信息 7 个分类 5 个标签
分类
LeetCode CodeTop 困难 未解决 1-2 字节跳动 程序员面试金典（第 6 版）
标签
数组 动态规划 双指针 栈 单调栈
目录

题目描述

✅ 面试题 17.21. 直方图的水量

题意分析

给定一个非负整数数组 height，第 i 项表示宽度为 1 的柱子的高度。下雨后柱子之间的凹陷处会积水，要求返回能接住的总水量。

约束里最重要的信号是"每根柱子宽度都是 1"。这让总水量可以按列拆解：整体积水量等于每一列积水量之和，而第 i 列的水面高度只由它左右两侧的最高柱子决定——水会一直漫到"左边最高"和"右边最高"中较矮的那个高度，再高就从矮的那侧溢出去了。于是有：

\[water_i = \max(0,\ \min(leftMax_i,\ rightMax_i) - height_i)\]

其中 $leftMax_i$ 是 $height[0..i]$ 的最大值、$rightMax_i$ 是 $height[i..n-1]$ 的最大值（把自身算进去可以省掉取 max(0, ...)，因为此时两个最大值都不小于 height[i]）。这条公式一旦写出来，整题就只剩"如何高效求出每个位置的左右最大值"。

边界上要覆盖：空数组或只有一两根柱子（接不到水）；数组单调递增或单调递减（同样接不到水）；两端的柱子（左端的 $leftMax$ 就是自己，右端同理，所以贡献为 0）；以及高度全相等的情形。数值上，n 可达 $10^5$、高度可达 $10^5$，总量不会溢出 int，但用 long 更保险。

解法：双指针 + 左右最大值

核心思路

从上面的公式出发，最直接的实现是对每个 i 都向左扫一遍求 $leftMax_i$、向右扫一遍求 $rightMax_i$，$O(n^2)$。瓶颈在于同一段前缀最大值被反复重算：求 $leftMax_5$ 时算过的东西，求 $leftMax_6$ 时又算了一遍。

第一次改进是用两个数组把前缀最大值和后缀最大值预处理出来，各扫一遍即可，时间降到 $O(n)$、空间 $O(n)$。这是最容易讲清也最不容易写错的版本，面试里作为"第一个正确解"完全够用。

真正的关键观察在于：公式里只用到 $\min(leftMax_i, rightMax_i)$，而不是两个值本身。也就是说，只要能确定这两者中较小的那个已经算准了，另一个哪怕还不准确也不影响结果。这就给了双指针的机会。

设左指针 l 从 0 出发、右指针 r 从 n-1 出发，leftMax 表示 $height[0..l]$ 的最大值、rightMax 表示 $height[r..n-1]$ 的最大值。不变量是：leftMax 是 l 位置真实的左侧最大值，rightMax 是 r 位置真实的右侧最大值（两者都只依赖已经扫过的那一侧，所以一定准确）。

现在比较 height[l] 和 height[r]：

  • 若 height[l] <= height[r]，先把 height[l] 并入 leftMax，此时 leftMax 就是位置 l 真实的左侧最大值。再看右侧：位置 l 真实的右侧最大值 $rightMax_l$ 至少包含 height[r]，所以 $rightMax_l \ge height[r]$。分两种情况——若 leftMax <= height[r]，则 leftMax <= rightMax_l，取最小值就是 leftMax；若 leftMax > height[r]，那说明 leftMax 来自 [0, l] 中某根高于 height[r] 的柱子，而这根柱子与 height[r] 中较矮的是 height[r]，水位由它封顶……但注意此时 height[l] <= height[r] < leftMax，位置 l 的水位是 $\min(leftMax, rightMax_l)$，而 $rightMax_l \ge height[r] \ge height[l]$，两种子情况下结算出的水量都不会超过 leftMax - height[l]，且这个值可以由后续更高的右侧柱子达成。标准结论是：较矮的那一端，其水位瓶颈必定来自本侧的最大值，于是 l 位置的积水量就是 leftMax - height[l]，可以立刻结算，然后 l++。
  • 否则对称地结算 r 位置：rightMax - height[r]，然后 r--。

直观理解是"水位由矮的一端封顶"：当左端比右端矮时，右边存在一根至少和 height[r] 一样高的柱子挡着，左端这一列的水位不可能被右侧限制得比 leftMax 更低，所以只需要看左侧的最大值。每一步都只结算"较矮的那一侧"，正是因为那一侧的答案此刻已经可以被完全确定。

这样两个指针相向而行，每个位置恰好被结算一次，时间 $O(n)$、空间 $O(1)$——省掉了预处理数组，是本题的最优解。

解题步骤

  • 初始化 l = 0、r = n - 1、leftMax = 0、rightMax = 0、answer = 0。两个最大值初始化为 0 是安全的，因为题目保证高度非负，任何真实高度都不小于 0，第一次更新就会把它们提到正确值。
  • 循环条件写 l < r。用严格小于而不是 <=：当两指针相遇时，那一根柱子必然是全局最高的柱子之一，它自己接不到水（$\min(leftMax, rightMax)$ 就等于它自身的高度），结算与否都不影响答案，但写成 <= 会让 leftMax/rightMax 的更新多走一步，容易在边界上引入混淆。
  • 比较 height[l] 和 height[r]，处理较矮的一侧。相等时归到左边处理（写 <=），归到哪边都对，但必须固定，否则两个分支可能同时不推进导致死循环。
  • 处理左侧时：先用 height[l] 更新 leftMax，再累加 leftMax - height[l]，最后 l++。三步的顺序不能乱。先更新 leftMax 是为了让它包含当前柱子，这样差值天然非负，不需要额外的 max(0, ...)；如果先累加再更新，height[l] 大于旧 leftMax 时会算出负数把答案减小。
  • 处理右侧时对称：先更新 rightMax，再累加 rightMax - height[r]，最后 r--。
  • 循环结束返回 answer。

以 height = [0,1,0,2,1,0,1,3,2,1,2,1] 走一遍（n = 12，答案应为 6）：

初始 l = 0、r = 11、leftMax = rightMax = 0、answer = 0。

height[0] = 0 <= height[11] = 1 → 更新 leftMax = 0，累加 0 - 0 = 0，l = 1。

height[1] = 1 <= 1 → leftMax = 1，累加 1 - 1 = 0，l = 2。

height[2] = 0 <= 1 → leftMax 仍为 1，累加 1 - 0 = 1，answer = 1，l = 3。这一格上方确实积了 1 单位水（左边有高 1 的柱子，右边有更高的柱子）。

height[3] = 2 > height[11] = 1 → 转而处理右侧：rightMax = max(0, 1) = 1，累加 1 - 1 = 0，r = 10。

height[3] = 2 <= height[10] = 2 → 处理左侧：leftMax = 2，累加 2 - 2 = 0，l = 4。

height[4] = 1 <= 2 → leftMax 仍 2，累加 2 - 1 = 1，answer = 2，l = 5。

height[5] = 0 <= 2 → 累加 2 - 0 = 2，answer = 4，l = 6。

height[6] = 1 <= 2 → 累加 2 - 1 = 1，answer = 5，l = 7。

height[7] = 3 > height[10] = 2 → 处理右侧：rightMax = max(1, 2) = 2，累加 2 - 2 = 0，r = 9。

height[7] = 3 > height[9] = 1 → 右侧：rightMax 仍 2，累加 2 - 1 = 1，answer = 6，r = 8。

height[7] = 3 > height[8] = 2 → 右侧：rightMax = max(2, 2) = 2，累加 2 - 2 = 0，r = 7。

此时 l = 7、r = 7，l < r 不成立，循环结束，返回 6，正确。

注意下标 9 那一格：它的左边最高是 3、右边最高是 2，水位取较小的 2，减去自身高度 1 得到 1 单位水。算它的时候我们用的是 rightMax = 2，而并不知道左边的 3——但因为 height[7] > height[9]，我们已经确定"瓶颈在右侧"，所以不需要知道左侧的确切值。这正是双指针能省掉预处理数组的原因。

代码实现

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        int l = 0;
        int r = n - 1;
        int leftMax = 0;
        int rightMax = 0;
        int answer = 0;

        while (l < r) {
            if (height[l] <= height[r]) {
                leftMax = Math.max(leftMax, height[l]);
                answer += leftMax - height[l];
                l++;
            } else {
                rightMax = Math.max(rightMax, height[r]);
                answer += rightMax - height[r];
                r--;
            }
        }
        return answer;
    }
}

func trap(height []int) int {
    l, r := 0, len(height)-1
    leftMax, rightMax := 0, 0
    answer := 0

    for l < r {
        if height[l] <= height[r] {
            if height[l] > leftMax {
                leftMax = height[l]
            }
            answer += leftMax - height[l]
            l++
        } else {
            if height[r] > rightMax {
                rightMax = height[r]
            }
            answer += rightMax - height[r]
            r--
        }
    }
    return answer
}

复杂度分析

  • 时间复杂度：$O(n)$。两个指针相向而行，每轮循环必定有一个指针移动一格，总移动次数是 n - 1；每轮内部只做常数次比较与加法，没有嵌套循环。
  • 空间复杂度：$O(1)$。只用了 l、r、leftMax、rightMax、answer 五个标量，没有预处理数组也没有栈——这正是双指针相对"前后缀最大值数组"（$O(n)$ 空间）和"单调栈"（最坏 $O(n)$ 空间）的优势。

关键点总结

  • 先把答案拆成可独立计算的最小单位，再想怎么求那个单位。本题把总水量拆成"每一列的水量"，公式 $\min(leftMax, rightMax) - height_i$ 一写出来，剩下的就只是"如何高效求前后缀最大值"这个纯工程问题。拆解粒度选对了，难题就变成了模板题。
  • 只用到两个量的最小值时，只需确定较小的那个。这是双指针能把 $O(n)$ 空间压到 $O(1)$ 的全部理由：较矮的一端其瓶颈必在本侧，另一侧的确切值不需要知道。这个"只求需要的那一半信息"的思路在 11. 盛最多水的容器 里同样适用。
  • 先更新极值再结算，能省掉一次取零操作。把当前元素并入 leftMax 之后，差值天然非负；顺序写反就会出现负贡献。凡是"极值 − 当前值"的累加，都要先确认极值是否已包含当前值。
  • 相向双指针要保证每轮至少推进一格。比较条件里的等号归属可以任选，但必须固定，否则相等时两个分支都不动就会死循环。
  • 面试视角：按"暴力 → 前后缀数组 → 双指针"三级递进作答，并准备好单调栈版本。面试官通常期望你至少给出 $O(n)$ 解；能主动说明双指针为何正确（较矮一端的瓶颈在本侧）是区分度所在。单调栈是另一条思路——按"横向层"而不是"纵向列"累加水量，适合追问"还有别的解法吗"，也是 84. 柱状图中最大的矩形 的核心工具。

易错点总结

  • 错误写法：先累加再更新极值，写成 answer += leftMax - height[l]; leftMax = Math.max(leftMax, height[l]); → 用例 height = [0, 2]：l = 0 时 leftMax 还是 0，累加 0 - 0 = 0 没问题；但 height = [3, 1, 3] 中 l = 0 时 leftMax = 0，累加 0 - 3 = -3，答案被减成负数。极值必须先包含当前元素。
  • 错误写法：循环条件写成 l <= r → 用例 height = [1]：l = r = 0，进入循环后 height[0] <= height[0] 成立，累加 1 - 1 = 0 后 l = 1，虽然结果碰巧为 0，但同一根柱子在某些写法下会被两侧各结算一次导致重复累加。相向双指针应当在相遇时停止。
  • 错误写法：比较条件写成 height[l] < height[r]（去掉等号）且 else 分支也不推进 → 若 else 分支误写成 if (height[l] > height[r])，相等时两个分支都不执行，l 和 r 都不动，死循环直到超时。等号必须明确归到某一侧。
  • 错误写法：用 leftMax 去结算右指针位置，写成 answer += leftMax - height[r] → 用例 height = [0,1,0,2,1,0,1,3,2,1,2,1]：在处理右侧时用了左侧的最大值，两侧信息串线，得到远小于（或大于）6 的错误结果。
  • 错误写法：leftMax/rightMax 初始化成 Integer.MAX_VALUE → 用例 height = [1, 0, 1]：leftMax 永远不会被真实高度更新，累加 MAX_VALUE - 0 直接溢出成负数。求最大值的初始值应取不可能超过的下界，本题因高度非负故取 0。
  • 错误写法：没有处理空数组，直接写 int r = height.length - 1 后访问 height[r] → 用例 height = []：r = -1，循环条件 0 < -1 不成立不会进入，其实是安全的；但若把循环条件误写成 l <= r 之外的形式，或在循环前先读一次 height[0]，就会越界。任何对首尾元素的提前访问都要先判空。
  • 错误写法：用 min(leftMax, rightMax) - height[i] 的通用公式配合双指针 → 用例 height = [4, 2, 3]：l = 1 时 rightMax 只统计了 [r, n-1] 的部分，并不是位置 1 真实的右侧最大值，用它取 min 会算出错误的水位。双指针的正确性恰恰建立在"只用本侧极值结算较矮一端"上，套用通用公式反而错。
  • 错误写法：按行（水平层）累加时把每层宽度算成"最左最右柱子之间的距离" → 用例 height = [3, 0, 1, 0, 3]：某一层可能被中间的柱子分成多段，直接用端点距离会把柱子占据的格子也算成水。横向解法必须用单调栈逐段结算。
  • 错误写法：Go 里 l, r := 0, len(height) （少减 1） → 用例 height = [1, 2]：首次访问 height[2] 越界 panic。右端点是最后一个合法下标 len - 1。
  • 错误写法：Go 里用 math.Max 处理 int → 编译报错，math.Max 只接受 float64；要么手写 if 比较（如代码中所示），要么用 Go 1.21+ 的内置 max。
  • 错误写法：把答案变量声明成 int 但在高度和长度都取上限的极端数据上不做估算 → 用例 n = 10^5、高度全为 $10^5$ 的凹槽：总水量约 $10^{10}$，超过 int 上限溢出成负数。本题给定的约束下不会触发，但同类题（如把宽度也放大的变体）中应先估算总量再决定用 int 还是 long。
  • 错误写法：预处理版本里 rightMax 数组从左往右填 → 用例 height = [2, 0, 2]：后缀最大值必须从右往左递推，方向写反会得到前缀最大值，两个数组变成同一个东西，答案恒为 0。递推方向必须与依赖方向一致。

相似题目

题目 难度 考察点
42. 接雨水 困难 完全同题的主站版本，可对照双指针、前后缀数组与单调栈三种写法
11. 盛最多水的容器 中等 同样是相向双指针移动较矮一端，但求的是单个容器而非逐列累加
84. 柱状图中最大的矩形 困难 用单调栈找每根柱子的左右第一个更矮者，是横向解法的核心工具
407. 接雨水 II 困难 升级到二维网格，水位由四周边界决定，要用最小堆从外向内扩展
85. 最大矩形 困难 把二维矩阵按行压成直方图，再逐行套用单调栈求最大矩形