lc42-Trapping Rain Water

發表於   |   分類於   |   0 comments   |   
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 l = height.size();
        stack<pair<int, int> > stk;
        int res = 0;
        vector<int> prev(l, 0);
        for (int i = 0; i < l; i++) {
            if (!height[i]) continue;
            if (!stk.empty()) {
                pair<int, int> last = stk.top();
                while (!stk.empty() && last.second <= height[i]) {
                    stk.pop();
                    res += (last.second - prev[last.first]) * (i-last.first-1);
                    // cout << i << " res="<<res<<endl;
                    if (!stk.empty())   prev[stk.top().first] = last.second;
                    if (!stk.empty())   last = stk.top();
                }
                if (last.second > height[i]) {
                    res += (height[i] - prev[last.first]) * (i-last.first-1);
                    // cout << i << " res="<<res<<endl;
                    prev[last.first] = height[i];
                }
            }
            stk.push(make_pair(i, height[i]));
        }
        return res;
    }
};

偷看答案，two pointers的方法太机智了。

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