接雨水

题目链接-Leetcode42题:接雨水

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：

示例 2：

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

2. 题解

本题的重点在于需要理解计算可接雨水区间的方式，在下列的方法中，方法1、2、3是一种计算的思路，即对于分别计算每个可接雨水区间的所接雨水数（竖向），方法4是另一种计算思路，即对于连续的可接雨水的区间按层计算所接雨水数（横向）。

2.1 方法1：暴力

直观想法

直接按问题描述进行。对于数组中的每个元素，我们找出下雨后水能达到的最高位置，等于两边最大高度的较小值减去当前高度的值。

算法

• 初始化ans = 0

• 从左向右扫描数组

  • 初始化max_left = 0和max_right = 0

  • 从当前元素向左扫描并更新

    • max_left = max(max_left,height[j])

  • 从当前元素向右扫描并更新

    • max_right = max(max_right,height[j])
  • 将min(max_left,max_right)-height[i]累加到ans（此处是计算柱子i可以积累多少雨水）

public int trap_force(int[] height){//暴力
    //找到左右两边的最大值
    int ans = 0 ;
    int n = height.length ;
    for( int i = 1; i < n -1 ;i++){ //注意遍历的范围
        int left_max = 0 , right_max = 0; //每次循环都需要重新找两边的最大值
        for(int j = i ; j >= 0;j--){
            left_max = Math.max(left_max,height[j]);
        }
        for (int j = i ; j < n ; j++){
            right_max = Math.max(right_max,height[j]);
        }
        ans += Math.min(right_max,left_max) - height[i];
    }
    return ans;
}

复杂度

• 时间复杂度： #card=math&code=O%28n%5E2%29)。数组中的每个元素都需要向左向右扫描。
• 空间复杂度 #card=math&code=O%281%29) 的额外空间。

2.2 方法2：动态编程

直观想法

在暴力方法中，我们仅仅为了找到最大值每次都要向左和向右扫描一次。但是我们可以提前存储这个值。因此，可以通过动态编程解决。

这个概念可以见下图解释：

算法

• 找到数组中从下标i到最左端最高的条形块高度 left_max。
• 找到数组中从下标 i 到最右端最高的条形块高度 right_max。

• 扫描数组height并更新答案：

  • 累加min(max_left[i],max_right[i])-height[i]到ans上

public int trap_stack(int[] height){
    //使用单调栈保存两侧边值

    int ans = 0 , n = height.length , current = 0;
    if( n == 0) return 0;
    Deque<Integer> sk = new LinkedList<>();
    while (current < n){
        while (!sk.isEmpty() && height[sk.peek()] < height[current] ){
            int top = sk.pop();
            if(sk.isEmpty()) break;
            int distance = current - sk.peek() - 1;
            int boundHeight = Math.min(height[current],height[sk.peek()]) - height[top];
            ans += distance * boundHeight;
        }
        sk.push(current++); //将当前处理的块放进去

    }
    return ans;
}

复杂度

• 时间复杂度：#card=math&code=O%28n%29)。

  • 存储最大高度数组，需要两次遍历，每次#card=math&code=O%28n%29) 。

  • 最终使用存储的数据更新ans ，#card=math&code=O%28n%29)。

• 空间复杂度：$O(n) $额外空间。

  • 和方法 1 相比使用了额外的 #card=math&code=O%28n%29) 空间用来放置 left_max和right_max 数组。

方法1和方法2的计算思路可以使用下图进行概述

2.3 方法3：双指针

直观想法（不是很懂）

和方法2相比，不从左和右分开计算，想办法一次遍历完成。

从dp方法的示意图中我们注意到，只要right_max[i]>left_max[i]（元素0到元素6），积水高度将由left_max决定，类似地left_max[i]>right_max[i]（元素8到11）。

所以我们可以认为如果一端有更高的条形块（如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧的条形块高度并不是最高的，我们则开始从相反的方向遍历（从右到左）。

我们必须在遍历时维护left_max和right_max，但是我们现在可以使用两个指针交替进行，实现1次遍历解题。

算法

• 初始化left =0 ,right = size-1

• while left < right , do :

  • if height[left] < height[right]（height[right]<=right_max）

    • if height[left] > left_max，更新left_max
    • else累加left_max-height[left]到ans
    • left = left +1

  • else（height[left]<=left_max）

    • if height[right]>=right_max，更新right_max
    • else累加right_max-height[right]到ans
    • right = right -1.

public int trap_pointer(int[] height){
    //使用双指针
    int ans = 0 , n = height.length , current = 0;
    if( n == 0) return 0;
    int left = 0 , right = n-1;
    int left_max = 0 , right_max = 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;
}

复杂性分析

• 时间复杂度：#card=math&code=O%28n%29)。单次遍历的时间#card=math&code=O%28n%29)。
• 空间复杂度：#card=math&code=O%281%29)的额外空间。left,right,left_max,right_max 只需要常数的空间。

2.4 方法4：栈

直观想法

可以不用像方法2那样存储最大高度，而是使用栈来跟踪可能储水的最长的条形块，使用栈就可以在一次遍历内完成计算。

在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块，我们将条形块的索引入栈，意思时当前的条形块被栈中的前一个条形块界定。如果发现一个条形块长于栈顶，我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定，因此可以弹出栈顶元素并累加答案到ans中。

算法

• 使用栈来存储条形块的索引下标

• 遍历数组

  • 当栈非空且height[current] > height[sk.top()]

    • 意味着栈中元素可以被弹出。弹出栈顶元素top

    • 计算当前元素和栈顶元素的距离，准备进行“填充雨水”操作：
      distance = current - sk.top() - 1

    • 找出界定高度
      bounded_height = min(height[current],height[sk.top])-height[top]

    • 向ans中累加积水量

  • 将当前索引下标入栈

  • 将current移动到下个位置

public int trap_stack(int[] height){
    //使用单调栈保存两侧边值
    int ans = 0 , n = height.length , current = 0;
    if( n == 0) return 0;
    Deque<Integer> sk = new LinkedList<>();
    while (current < n){
        while (!sk.isEmpty() && height[sk.peek()] < height[current] ){
            int top = sk.pop();
            if(sk.isEmpty()) break;
            int distance = current - sk.peek() - 1;
            int boundHeight = Math.min(height[current],height[sk.peek()]) - height[top];
            ans += distance * boundHeight;
        }
        sk.push(current++); //将当前处理的块放进去

    }
    return ans;
}

复杂性分析

• 时间复杂度：#card=math&code=O%28n%29)。

  • 单次遍历 #card=math&code=O%28n%29)，每个条形块最多访问两次（由于栈的弹入和弹出），并且弹入和弹出栈都是 #card=math&code=O%281%29)的。
• 空间复杂度：#card=math&code=O%28n%29)。 栈最多在阶梯型或平坦型条形块结构中占用#card=math&code=O%28n%29)的空间。

流程模拟