接雨水

​

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

https://uploadfiles.nowcoder.com/images/20210416/999991351_1618541247169/26A2E295DEE51749C45B5E8DD671E879

解题代码

 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

class Solution {
public:
    /**
     * max water
     * @param arr int整型vector the array
     * @return long长整型
     */
    long long maxWater(vector<int>& arr) {
        // write code here
        int n = arr.size();
        if (n==0) return 0;
        int l=0,r = n-1;
        int h = min(arr[l],arr[r]);
        long long res = 0;
        while(l<r) {
            if(arr[l] < arr[r]) {
                l++;
                if (arr[l] < h) {
                    // 出现凹
                    res += (h-arr[l]);
                }else {
                    // 出现凸
                    h = min(arr[l],arr[r]);
                }
            }else {
                r--;
                if(arr[r] < h) {
                    //凹
                    res += (h - arr[r]);
                    
                }else {
                    //凸
                    h = min(arr[l],arr[r]);
                }
            }
        }
        return res;
   }
};