LeetCode 接雨水 Trapping Rain Water 积水问题

小灰灰 2022-05-28 02:47 107阅读 0赞

# 中文题目 #

使用两根指针：给定 n 个非负整数表示每个宽度为1的柱子的高度图，计算下雨之后能接多少水。给定 *n* 个非负整数表示每个宽度为1的柱子的高度图，计算下雨之后能接多少水。

例如，  
输入 `[0,1,0,2,1,0,1,3,2,1,2,1]`，返回 `6`。

![rainwatertrap.png][]

上面的高度图由数组 \[0,1,0,2,1,0,1,3,2,1,2,1\] 表示，在这种情况下，可以接 6 个单位的雨水（蓝色部分）。

# 英文题目 #

Given *n* non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

For example,

Given `[0,1,0,2,1,0,1,3,2,1,2,1]`, return `6`.

### 复杂度 ###

时间 O(N) 空间 O(1)

### 思路 ###

使用两根指针：

1. 一根从右往左，更新记录从位置i往右边的峰值;

2. 一根从左往右遍历。更新从位置i往左边峰值的同时，计算位置i处可以积水多少;

3. 水面高度h应为min(maxL,maxR)。积水应为max(0,h-height\[I\]);

### 代码 ###

class Solution {
        public int trap(int[] height) {
            if(height == null || height.length <= 2)
                return 0;
            int maxL = height[0];
            int[] maxRs = new int[height.length];
            int waterSum = 0;//计算总的水量
            int maxR = 0;
            for(int i = height.length - 1; i >= 0; i--){
                if(height[i] > maxR) {
                    maxRs[i] = maxR = height[i];
                }
                else {
                    maxRs[i] = maxR;
                }
            }
            for(int i = 1; i < height.length - 1; i++){
                if(height[i] > maxL) {
                    maxL = height[i];//更新左边最大值
                }
                    waterSum += Math.max(Math.min(maxL, maxRs[i]) - height[i], 0);
            }
            return waterSum;
            
          }
    }

[rainwatertrap.png]: https://leetcode-cn.com/static/images/problemset/rainwatertrap.png