Leetcode 42. Trapping Rain Water

发表于 | 分类于

https://leetcode.com/problems/trapping-rain-water/

第一种解法是单调栈

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
class Solution {
public:
    int trap(vector<int>& height) {
        // 边界情况判定
        if(height.size() < 2){
            return 0;
        }
        
        stack<int> s;
        int res = 0;
        int cur = 0;
        while(cur < height.size()){
            //栈内的元素是单调递增的
            while(!s.empty() && height[cur] > height[s.top()]){
                // 当遍历的到元素比当前栈顶元素值大时，计算此时的蓄水量
                int top = s.top();
                s.pop();
                if(s.empty()){
                    break;
                }
                
                int dist = cur - s.top() - 1;
                int bound = min(height[cur], height[s.top()]) - height[top];
                
                res += dist * bound;
            }
            s.push(cur++);
        }
        
        return res;
    }
};

第二种解法是双指针

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
class Solution {
public:
    int trap(vector<int>& height) {
        if(height.size() < 2){
            return 0;
        }
        
        int res = 0;
        int length = height.size();
        // 分别从头和尾开始的指针
        int left = 0, right = length - 1;
        int left_max = 0, right_max = 0;
        while(left < right){
            if(height[left] < height[right]){
                height[left] >= left_max ? left_max = height[left] : res += left_max - height[left];
                left++;
            }
            else{
                height[right] >= right_max ? right_max = height[right] : res += right_max - height[right];
                right--;
            }
        }
        
        return res;
    }
};
0%