By

文章目录
  1. 1. 题目
  2. 2. 解法
  3. 3. 参考

题目

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）


解法

双指针法：
如果一端有更高的条形块（例如右端），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
我们必须在遍历时维护 $\text{leftMax}$ 和 $\text{rightMax}$，但是我们现在可以使用两个指针交替进行，实现 1 次遍历即可完成。

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
#include<iostream>
#include<vector>
using namespace std;

int trap(vector<int>& height) {
    if(height.size()<=2){
        return 0;
    }

    int left_max = height[0];
    int right_max = height[height.size()-1];
    int i = 0,j = height.size()-1;
    int sum = 0;

    while(i<=j){
        cout << "i:"<<i << " j:"<<j<<endl;
        if(left_max <= right_max){
            if(height[i]>=left_max){
                left_max = height[i];
            }else{

                cout << "left: " << left_max << ":" << height[i] << endl;
                sum += left_max-height[i];
            }
            ++i;
        }else{
            if(height[j] >= right_max){
                right_max = height[j];
            }else{
                cout << "right: " << right_max << ":" << height[j] << endl;
                sum += right_max - height[j];
            }
            --j;
        }
    }

    return sum;
}



int main(){
    //int num1[] = {0,1,0,2,1,0,1,3,2,1,2,1};
    int num1[] = {5,5,1,7,1,1,5,2,7,6};
    vector<int> vec1(num1,num1+10);


    cout << trap(vec1) << endl;
	
	return 0;
}

参考

  1. https://leetcode-cn.com/problems/trapping-rain-water/
  2. https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
文章目录
  1. 1. 题目
  2. 2. 解法
  3. 3. 参考