LeetCode/Trapping_Rain_Water.cpp at master · Wilson1211/LeetCode · GitHub

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
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#include <iostream>

using namespace std;

int arr[30001];
int mm_idx[30001];
int dp[30001];

int call(int a, int b, int h);

int main(){

    int n;
    int max = 0, mmlen=0;
    int h1, ptr1;
    cin >> n;

    for(int i=0;i<n;i++) {
        cin >> arr[i];
    }

    dp[n-1] = n;
    for(int i=n-2;i>=0;i--) {
        h1 = arr[i];
        dp[i] = n;
        int j = i+1;
        while(j<n){
            if(h1 <= arr[j]){
                dp[i] = j;
                break;
            }
            j = dp[j];
        }

    }

    int sum = 0;
    for(int i=0;i<n-1;) {
        int ptr1 = dp[i];
        if(ptr1 == n){
            int j = i+1;
            while((dp[j] != n)) {
                j = dp[j];
            }
            sum += call(i+1, j-1, arr[j]);
            //cout<<"a: "<<i+1<<" b: "<<j-1<<" arrj:"<<arr[j]<<endl;
            i = j;

        }else{
            sum += call(i+1, ptr1-1, arr[i]);
            //cout<<"a1: "<<i+1<<" b1: "<<ptr1-1<<" arri:"<<arr[i]<<endl;
            i = ptr1;
        }
    }


    cout<<"sum: "<<sum<<endl;

}

int call(int a, int b, int h){
    if(a>b) return 0;
    int tmp = 0;
    for(int i=a;i<=b;i++){
        tmp += arr[i];
    }
    return h*(b-a+1)-tmp;
}