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

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

题目描述

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

image-20260929105939545

题意分析

每根柱子宽度为 1，高度非负，求整排柱子能接住的总水量。某一列的水位由它左右两侧的最高柱子共同限制，不能只根据相邻柱子判断。

解法：双指针结算较矮一侧

核心思路

[!blue]

对第 i 列，若左右最大高度都包含当前柱子，水量就是 min(左侧最大高度, 右侧最大高度) - height[i]。要在常数空间中计算，可以从两端向内逐列结算：leftMax、rightMax 分别保存已经处理的左侧、右侧最高柱子。

这里比较的是当前两端的柱高。其依据是一个不变量：所有已移出区间的柱子，都不高于当前两端中较高的一根。初始没有已移出的柱子；每次移走较矮端点，较高端点仍留在区间内，足以继续覆盖此前已移出柱子的高度，因此该性质一直成立。

若 height[l] <= height[r]，将当前左柱纳入 leftMax 后，它就是这一列完整的左侧最高值。根据上述不变量，它不会高于当前右柱；而这一列真正的右侧最高值至少是当前右柱。因此较低的边界一定是 leftMax，可以立即累加 leftMax - height[l]，无需知道右边其余柱子的精确最大值。右端较矮时对称地结算 rightMax - height[r]。

每轮只结算一个端点并移动对应指针，所以所有已处理列都恰好计入一次。两指针相遇时，剩下的柱子不低于所有已移出的柱子，是整段的一个最高点，自身水量为 0，可以结束。空数组或只有一根柱子时循环不执行，答案同样为 0。

解题步骤

  1. 令 l = 0、r = n - 1，两侧最大值和答案均初始化为 0。
  2. 当 l < r 时比较当前端点高度。
  3. 左端不高于右端时，先更新 leftMax，再累加本列高度差，然后将 l 加 1；否则对右端执行对称操作。
  4. 指针相遇后返回总水量。高度相等时代码固定处理左端，也能保持不变量并推进循环。

代码实现

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)$。每轮向内移动一个指针，每个位置最多结算一次。
  • 空间复杂度：$O(1)$。只维护指针、两个历史最大值和答案。

关键点总结

[!green]

  • 每列水位取左右最高边界中的较小值，当前柱子本身也包含在最大值中。
  • 较高端点保证另一侧已有足够高的边界，使较矮端点能够立即结算。
  • 先把当前柱子纳入本侧最大值，再做减法，贡献才始终非负。

易错点总结

[!yellow]

  • 先累加高度差再更新最大值，新出现的更高柱子会产生负贡献。
  • 不能直接用另一侧尚未完整统计的历史最大值结算，本实现依赖当前较高端点提供的边界。
  • 相等高度也要移动一侧指针，否则循环会停在原地。
  • 每列宽度固定为 1，只需累加水深；不能套用两根柱子围成容器的宽度乘法。

相似题目

题目 难度 关联与区别
407. 接雨水 II 困难 从一维左右边界推广到二维四邻边界，原题需要最小堆从最低外边界向内扩散。
11. 盛最多水的容器 中等 两题都受较低边界限制，但容器题只选两柱，接雨水要汇总每个位置的水深。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2021/10418518
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！