经典面试题——接雨水的四种解法

Leetcode刷题
留言

接雨水这道题目是非常经典的面试题，师兄字节面试的时候似乎就碰到了，所以把它抽出来研究了一下，主要是学习参考Leetcode上的各种评论和题解，总结了四种方法，其中三种是按列计算，还有一种是按区域行计算。最后一种方法虽然复杂度上没有双指针法简单，但是如果给我们的数组是流式输入，无法从后往前进行遍历的话，就只有最后一种方法有用了。

42 接雨水

题目描述

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

示例1：

image-20210401111657293.png

输入： 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$

  • $0 <= n <= 3 \times 10^4$

  • $0 <= height[i] <= 10^5$

解法一：暴力法

核心思路

仔细思考每一个单位的雨水高度的特点，可以发现对于每个单位而言，雨水的高度就是该单位左右最高高度中的较小值和自己高度的差(注意要从自己本身找起)。所以用暴力法，找到每一个单位左右最高高度，然后用两者中较小的高度减去自己的高度，然后将所有高度的水的高度相加，就得到了能接的雨水的总量。

关键就在于发现单位处的雨水高度就是左右最高处较小值和自己高度的差。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution{
public:
    int trap(vector<int> &height){
		int ans = 0;
        int n = height.size();
        for(int i=1;i<n-1;i++){
            int left_high=0 , right_high=0;
            for(int j=i;j>=0;j--){
                left_high = max(left_high,height[j]);
            }
            for(int j=i;j<n;j++){
                right_high = max(right_high,height[j]);
            }
            ans += min(left_high,right_high)-height[i]
        }
    	return ans;
	}  
};

复杂度分析

  • 时间复杂度： $O(n^2)$。数组中的每个元素都需要向左向右扫描。
  • 空间复杂度：$O(1)$ 的额外空间

解法二：双指针

核心思路

在暴力法中，之所以称“暴力”是因为我们在遍历数组中的每个高度时，都要在左右找最高的格子。时间复杂度一下子就上来了。那么有没有一种方法可以让我们不用在遍历中再进行遍历找最高值呢？双指针法就是针对一次遍历进行设计的算法。

上一种解法我们还可以这样理解：

  • 当我们从左往右进行遍历高度时，我们很容易得到到目前为止，我的左侧最高的高度，而如果此时我们知道了我们的右侧，无论哪个位置，出现了一个比我的左侧最高高度还高的高度，那显然我目前所在的位置如何填充就也知道了。

同理，那我们如果从右往左进行遍历时，也是知道右侧最高高度，而不知道左侧高度。一旦知道左侧高度，我们同样也就知道了右侧该如何填充。

那我们使用两个指针，从左右两端往中间进行扫描，是不是可以一次遍历解决问题呢？

当然会存在一个问题，因为我们左右指针分别找的是指针当前所在位置的最高高度，当前位置的最高高度显然不一定是对方所需要的左/右侧最高高度。但注意的是，我们也没有必要一定找到最高高度，我们只需要知道另一侧存在比自己已知那一侧的最高高度还要高的高度就可以了。

所以我们的思路就是用两个指针分别从两端进行遍历，用两个变量分别记录左右侧最高的高度。我们需要保证每次移动的指针所在这一侧的最高高度必然是小于等于另一侧最高高度的，只有这样，我们才可以保证我们的指针在走动时，可以知道当前位置会不会积攒雨水。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution{
public:
    int trap(vector<int>& height){
		int left=0,right=height.size()-1;
        int left_max=0,right_max=0;
        
        while(left<right){
            left_max = max(left_max,height[left]);
            right_max = max(right_max,height[right]);
            
            if(left_max<right_max){
                ans += left_max-height[left];
                left++;
            }else{
                ans += right_max-height[right];
                right--;
            }
        }
        return ans;
    }
};

复杂度分析

  • 时间复杂度： $O(n)$。一次遍历解决问题
  • 空间复杂度：$O(1)$ 的额外空间

解法三：动态规划

核心思路

在解法一中我们介绍了这道题的最直接的想法，也就是每个元素都要向两边进行扫描找最大值，所以就会有$O(N^2)$的时间复杂度。那么我们可以考虑使用额外的空间来存储最大值的话，就不需要遍历每个元素都要扫描了。而且，显然相对于数组部分元素的最大值，最大值是动态变化的，这是符和动态规划的思想的。

我们创建两个长度为n的数组$leftdp$和$rightdp$，对于$leftdpi$表示下标i及其左侧最大的高度，对于$rightdpi$表示下标i及其右侧最大的高度。

很容易看出来$leftdp[0]==rightdp[0]$,$leftdp[n-1]==rightdp[n-1]$。

然后其余数组元素计算遵循下列规则：

  • 当$1<=i<=n-1$时，$leftdp[i]==max(leftdp[i-1],height[i])$
  • 当$0<=i<=n-2$时，$rightdp[i]==max(rightdp[i+1],height[i])$

所以我们可以正向遍历数组得到$leftdp$的每个元素值，反向遍历数组得到数组$rightdp$的每个元素值。

得到两个动态规划数组后，能接的水的量就是$min(leftdp[i],rightdp[i])-height[i]$。然后一遍遍历就可以得到接水总量。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    int trap(vector<int>& height) {
		int n = height.size();
        if (n == 0) {
            return 0;
        }
        vector<int> leftdp(n);
        vector<int> rightdp(n);
        
        leftdp[0] = height[0];
        rightdp[n-1] = height[n-1];
        
        for(int i=1;i<n;i++){
            leftdp[i] = max(leftdp[i-1],height[i]);
        }
        for(int i=n-2;i>=0;i--){
            rightdp[i] = max(rightdp[i+1],height[i]);
        }
        
        int ans = 0;
        
        for(int i=0;i<n;i++){
            ans += min(leftdp[i],rightdp[i])-height[i];
        }
       
        return ans;
    }
};

复杂度分析

  • 时间复杂度：$O(n)$，其中 n 是数组 $height$的长度。计算数组$leftdp$和$rightdp$的元素值各需要遍历数组$height$一次，计算能接的水的总量还需要遍历一次。

  • 空间复杂度：$O(n)$，其中 n 是数组 $height$的长度。需要创建两个长度为 n 的数组$leftdp$和$rightdp$

解法四：单调栈

核心思路

为什么这道题可以想到使用单调栈呢？我们知道单调栈是一种很特殊的数据结构，他要求栈中存放的数据是有序的，分为单调递增栈和单调递减栈。

单调栈的特性要求它一定要在每次入栈操作时对栈内元素进行一个调整，总的来说就是要保证最大/最小元素一定要在栈底的位置，然后向栈顶依次递减。我们以单调递增栈为例，当第一个元素要入栈是可以随便入栈，但是当第二个元素来入栈时，我们就要考虑把上一个元素进行出栈才可以让第二个元素入栈。而假如栈中元素为两个，此时来了一个元素，比栈顶大而比栈底小，比如三个元素为5 1 3，我们就需要把第二个元素出栈，才可以把第二个元素入栈。

形如[5 1 3]这样的构造的元素组，和我们在这个题中需要填充雨水的数组完全一致，所以我们就可以考虑利用单调栈的调整过程，计算会积攒雨水的位置以及积攒雨水的多少。

那么到底是怎么计算雨水的呢？前面我们介绍的三种方法都是按列进行计算，但是此方法中确是以区域行的计算模式进行计算。比如形如[2,1,0,1,3]的数组，我们是当第四个数字来的时候，将第三个数字填充了1格雨水，然后再第五个数字来的时候，才将第二、第三和第四格各自填充了一单位雨水也就是三单位雨水进行计算的。

也就是说我们在计算雨水时，不仅仅需要height的值，也需要有下标的值，因为我们需要$长\times宽$才能计算出来区域行的雨水数量。那么我们的栈中可以考虑不存放height值，而是存放下标值，通过数组来得到height值。这样就可以看到长和宽的值。

具体单调栈的处理逻辑，如下所示：

遍历所有的柱子，并尝试入栈，入栈条件是当前遍历的元素小于栈顶元素的高度。如果当前遍历的元素等于栈顶元素，那么我们就需要更新栈顶元素，因为相同高度的柱子，需要下标最大的那个来计算宽度。

如果当前遍历的元素大于栈顶元素，类似于我们上面所说的5 1 3的情况，我们就要取栈顶元素，将栈顶元素弹出，作为要求水量的宽度以及长度的决定因素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
public:
    int trap(vector<int>& height) {
		int n = height.size();
        if(n<=2)
            return 0;
        stack<int> stk;
        stk.push(0);
        for(int i=1;i<n;i++){
            if(height[i]<height[stk.top()])
                stk.push(i);
            if(height[i]==height[stk.top()]){
                stk.pop();
                stk.push(i);
            }else{
                while(height[i]>height[stk.top()] && !stk.empty()){
                    int mid = stk.top();
                    stk.pop();
                    if(!stk.empty()){
                        int h = min(height[stk.top()],height[i])-height[mid];
                        int w = i-stk.top()-1;
                        sum += h*w;
                    }
                }
                stk.push(i);
            }
        }
        return sum;
    }
};
// 整理后
class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        stack<int> monstk;
        
        for(int i=0;i<height.size();i++){
        	while(!monstk.empty() && height[i]>height[monstk.top()] ){
                int top = monstk.top();
                monstk.pop();
                if(monstk.empty())
                    break;
                int left = monstk.top();
                int width = i-left-1;
                int heigh = min(height[left],height[i])-height[top];
                ans += width * heigh;
            }   
            monstk.push(i);
        }
        return ans;
    }
};

复杂度分析

时间复杂度：$O(n)$，其中 n 是数组 $height$ 的长度。从 0 到 n-1 的每个下标最多只会入栈和出栈各一次。

空间复杂度：$O(n)$，其中 n 是数组 $height$ 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。