LeetCode42-Trapping Rain Water

1、题目大意

给定n个非负整数，每个整数代表墙的高度，墙于墙凹泄处可以装雨水，问能装几个单位的雨水。

image-20200704205505481

image-20200704210037436

例如：[0,1,0,2,1,0,1,3,2,1,2,1]，答案为6

例如：[4,2,1,0,3,1,2,5]，答案为15

2、思路

分析题目，目的是要求出所有凹槽大小和。

那么我的想法是这样的，设置一个单调递减栈。

1、如果当前压入栈的元素小于栈顶元素，即直接将该元素加入栈。

2、如果当前压入栈的元素大于栈顶元素，即需要更新栈内元素，不断弹出栈顶元素直到栈顶元素大于当前元素大小或栈为空。那么在弹出时计算已填充墙的大小，再用总面积减去墙的大小。

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
class Solution {
    struct Node {
      int val;
      int index;
    };
public:
    int trap(vector<int>& height) {
        int n = height.size();
        Node sta[n + 5];
        int ans = 0;
        int l, r;
        int tail = -1;
        for(int i = 0; i < n; i++) {
            int sum = 0;
            l = -1;
            r = i;
            while(tail > -1 && height[i] >= sta[tail].val) {
                tail--;
                if(tail == -1)break;
                sum += (sta[tail + 1].index - sta[tail].index) * sta[tail + 1].val;
                l = sta[tail].index;
            }
            if(l != -1) {
                ans += (r - l - 1) * min(height[i], height[l]) - sum;
            }
            sta[++tail].val = height[i];
            sta[tail].index = i;
        }
        return ans;
    }
};

最后更新： 2020年07月04日 22:12

原始链接： http://tanruidd.github.io/2020/07/04/leetcode42-Trapping-Rain-Water/