力扣经典150题第十六题：接雨水

用户8589624

发布于 2025-11-13 15:43:32

980

文章被收录于专栏：nginxnginx

力扣经典150题第十六题：接雨水

1. 题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。示例 2：

输入：height = [4,2,0,3,2,5] 输出：9

提示：

n == height.length 1 <= n <= 2 * 104 0 <= height[i] <= 105

2. 问题分析

接雨水的问题可以使用双指针或者栈来解决。这里我们介绍使用双指针的解法。

3. 解题思路

使用两个指针 left 和 right 分别从数组的两端向中间移动。
定义变量 left_max 和 right_max 分别表示左侧和右侧的最大高度。
使用变量 ans 来累计接到的雨水量。
如果 height[left] < height[right]，则更新 left 端，否则更新 right 端。
每次移动指针时，更新对应一侧的最大高度，并根据当前柱子的高度和最大高度的关系计算接到的雨水量并累加到 ans 中。

4. 代码实现

class Solution {
    public int trap(int[] height) {
        int left = 0, right = height.length - 1;
        int left_max = 0, right_max = 0;
        int ans = 0;
        
        while (left < right) {
            if (height[left] < height[right]) {
                if (height[left] >= left_max) {
                    left_max = height[left];
                } else {
                    ans += left_max - height[left];
                }
                left++;
            } else {
                if (height[right] >= right_max) {
                    right_max = height[right];
                } else {
                    ans += right_max - height[right];
                }
                right--;
            }
        }
        
        return ans;
    }
}