runtime 7 ms, beats 99.76% of cpp submissions
O(n) solution with explanation

tags: two pointer

Trapping Rain Water

📖 description

給定一個陣列，表示每格建築物的高度，請求空格可儲水的大小。

ex.
    Input: height = [0,1,0,2,1,0,1,3,2,1,2,1]
    Output: 6
    Explanation: 
    The above elevation map (black section) is represented by array 
    [0,1,0,2,1,0,1,3,2,1,2,1]. 
    In this case, 6 units of rain water (blue section) are being trapped.

🧠 solution

Container With Most Water
solution
本題的題解很像上面那題，但當以 two pointer 的想法去思考時，比較難想到解法的，但其實只需要修改移動指標的狀態就結束了，我們會在左右各維護一個 max ( lmax , rmax )，分別表示左右兩邊的當前最大值，當遇到比較小的數值時，表示這格可以放水，而因為我們一直維護最小的那邊移動，所以可以確保另一邊一定是比較高的牆，所以水一定是可以被夾住的。

⏳ time complexity

掃過一次陣列，時間複雜度為 O(n)
總時間複雜度 O(n)

📝 code

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>& h) {
        int l = 0,r = h.size()-1;
        int lmax = 0,rmax = 0;
        int ans = 0;
        while(r>l){
            if(h[l]<h[r]){
                if(h[l]>=lmax){
                    lmax = max(lmax,h[l]);
                }
                else{
                    ans+=(lmax-h[l]);
                }
                l++;
            }
            else{
                if(h[r]>=rmax){
                    rmax = max(rmax,h[r]);
                }
                else{
                    ans+=(rmax-h[r]);
                }
                r--;
            }
        }
        return ans;
    }
};