本文共 2258 字，大约阅读时间需要 7 分钟。

题目

给定 n 个非负整数表示每个宽度为 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 个单位的雨水（蓝色部分表示雨水）。

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

输出：9

n == height.length

0 <= n <= 3 * 104

0 <= height[i] <= 105

一、栈

题解

/*** 当左右两侧的柱子都比中间高时，就可以接住雨水，记录其中一个的位置，* 就可以只去寻找下一个除记录位外比左侧更高的柱子* 寻找下一个更大的值、寻找下一个更小的值，属于单调栈的范畴** 对更低的柱子，如果后面能找到更高的柱子，就能接到雨水，所以入栈把它保存起来* 当出现高于栈顶的柱子，说明可以对前面的低柱子进行计算，同时将它们出栈* 每次计算的是一个横条的水块面积*/

时间复杂度：所有高度方块最多入栈出栈一次，时间复杂度为O(n)。

空间复杂度：所有n个高度方块占据不多于n个空间，空间复杂度为O(n)。

实现

public int trap(int[] height) {        Deque
   
     stack = new LinkedList<>();        int sum = 0;        for(int i = 0; i < height.length; i++) {            // 当栈不为空且比左侧更高时，可以开始结算            while(!stack.isEmpty() && height[i] > height[stack.peek()]) {                // 别忘了记录要出栈的数据                int curr = stack.peek();                stack.pop();                if(stack.isEmpty()) {                    break;                }                int left = stack.peek();                int right = i;                // 这是一个横向长条面积，相当于从底层向上层层计算                int waterH = Math.min(height[left], height[right]) - height[curr];                sum += (right - left - 1) * waterH;            }            // 对更低的柱子，如果后面能找到更高的柱子，就能接到雨水，所以入栈把它保存起来            stack.push(i);        }        return sum;                                         }
   

二、双指针

题解

/*** 使用双指针从左右两边扫，可以视为左右两侧各有一个夹板* 谁的高度更高，谁就能替对方挡下雨水，因此雨水的高度也将由对方决定，即:* 如果height[left] < height[right], 则必有leftMax < rightMax, 下标left处能接到的雨水等于leftMax-height[left]** 每一列雨水的高度取决于 该列 左侧最高的柱子和 右侧最高的柱子中 最矮的那个柱子的高度* 每次计算的是一个竖条的水块面积*/

时间复杂度：数组只遍历一次，时间复杂度O(n)。

空间复杂度：只记录常量个数据，空间复杂度O(1)。

实现

public int trap(int[] height) {        int sum = 0;        int left = 0;        int right = height.length - 1;        int leftMax = 0;        int rightMax = 0;        while(left < right) {            // 记录左右两侧遍历到的最高挡板            leftMax = Math.max(leftMax, height[left]);            rightMax = Math.max(rightMax, height[right]);            if(height[left] < height[right]) {                sum += leftMax - height[left];                ++left;            }else {                sum += rightMax - height[right];                --right;            }        }        return sum;

转载地址：http://gxvli.baihongyu.com/