42 . Trapping Rain Water

我們首先先想, 水要怎麼樣才會留住, 直接可以想到的是, 可以去看當前左邊最大值, 跟當前右邊的最大值, 兩者取最小值, 是否都還比當前高

如上圖, 當前值為1, 左邊最大值是2, 右邊最大值是3, 合理我們可以推斷, 至少被夾住了, 可以留住 2–1的水空間

code:

我們可以用兩個vector, 紀錄 當前位置的右邊最大值, 跟當前位置的左邊最大值, 最後在來看是否可以留住水, 便可以解決這題

class Solution {
public:
    int trap(vector<int>& height) {
        int ret =0;
        int n = height.size();
        std::vector<int> table_lr(n ,0);
        std::vector<int> table_rl(n, 0);
        int cur_mx = 0;
        // left max table
        for(int i = 0; i < n;i++){
            table_lr[i] = cur_mx;
            cur_mx = max(height.at(i), cur_mx);
        }
        cur_mx = 0;
        // right max table
        for(int i =  n -1; i >= 0;i--){
            table_rl[i] = cur_mx;
            cur_mx = max(height.at(i), cur_mx);
        }
        // calculate result
        for(int i = 0; i < n;i++){
            if(height.at(i) < min(table_lr[i], table_rl[i])){
                ret +=  min(table_lr[i], table_rl[i]) - height.at(i);
            }
        }
        return ret;
    }
};

但其實在看第二張表的時候, 我們就可以即時反應那個位置的結果, 節省掉最後一次迴圈的功, 除此外還可以省掉一個紀錄table, code如下

class Solution {
public:
    int trap(vector<int>& height) {
        int ret =0;
        int n = height.size();
        std::vector<int> table_lr(n ,0);
        int cur_mx = 0;
        // left max table
        for(int i = 0; i < n;i++){
            table_lr[i] = cur_mx;
            cur_mx = max(height.at(i), cur_mx);
        }
        cur_mx = 0;
        // get right max amd calclate result
        for(int i =  n -1; i >= 0;i--){
             if(height.at(i) < min(table_lr[i], cur_mx)){
                ret +=  min(table_lr[i], cur_mx) - height.at(i);
            }
            cur_mx = max(height.at(i), cur_mx);
        }
return ret;
    }
};

時間複雜度為O(n), 空間複雜度:O(n)

還有一種方法, 是從左右指標逼近, 一開始我看到這作法, 完全不知道這是怎麼運作的

我們在這個陣列的頭尾用指標追蹤, 我們一開始就直接比較兩值(A, C)的大小, 若左邊(A)比較小, 將左邊(A)直接往右移(B), 並當右邊這個值(B), 若比左邊的值(A)小, 我們合理推斷至少可以裝(A-B)的水, 若比較大, 我們就更新左邊的值(A->B)

???為什麼, 我們壓根兒不知道另一邊的牆是否能擋住阿, 原因是因為我們一開始就做兩邊極值的比較(min(A, C)), 所以當B比較小, 可以確保另一邊(C > A>B), 一定擋得下來

蠻有趣的, 可以推倒看看, 另一個方向亦同

class Solution {
public:
    int trap(vector<int>& height) {
        int ret =0;
        int n = height.size();
        int l = 0;
        int r = n - 1;
while(l < r){
          int cur_min = min(height.at(l), height.at(r));
          if(cur_min == height.at(l)){
              l++;
              while(l<r && cur_min > height.at(l)){
                  ret+= cur_min - height.at(l++) ;
}
          }else{
              r--;
              while(l<r && cur_min > height.at(r)){
                  ret+=  cur_min - height.at(r--);
}
          }
        }
      
        return ret;
    }
};

我們可以收一下code

class Solution {
public:
    int trap(vector<int>& height) {
        int ret =0;
        int n = height.size();
        int l = 0;
        int r = n - 1;
        int cur_min = 0;
        while(l < r){
            int lower = height[height.at(l) <= height.at(r)?l++:r--];
            if(lower > cur_min){
                cur_min = lower;
            }else{
                ret += cur_min - lower;
            }
        }
        return ret;
    }
};

時間複雜度O(n), 空間複雜度O(1)

在寫 84題時, 一直覺得他們很像, 原來還有這種stack的用法

看網路上有人說更簡單…, 其實我覺得這才是他要考你的題目, 但其實也更難了

首先, 我們會去建立一個stack,

這個stack有幾個特性

1.當stack為空的時候,  無條件加入
2.紀錄所有牆的index

我們就走訪一次整個陣列

當遇到當前(A)的牆比stack最上層的元素(B)還高時, 先把它取出來, 並且留著

我們接下去看stack裡面次高的元素(C), 肯定是會 >B的, 所以在A,C之間一定可以存到水

我們就用 min(A, C)- B, 接著在乘上AC之間的距離, 這一動, 困惑我好久

我們畫一個圖, 會比較好理解

當我們在看

這一動時, 由於接下來的1 > 0, 所以我們就會執行一次操作

得到的結果為

在下一動 同樣都是1的高度, 所以沒有水可以存, 我們把舊的1 pop out, 放新的1進去

最後往前

過程就先省略, 但最後就可以在高度三跟高度二之間的水存下來, 而下面那塊早在上面的步驟就已經完成了

這個用圖好理解很多

class Solution {
public:
    int trap(vector<int>& h) {
        h.push_back(0);
        stack<int>st;
        int res = 0;
        for(int i = 0; i < h.size();i++){
            while(!st.empty() && h[st.top()] < h[i]){
                int cur = h[st.top()];
                st.pop();
                if(!st.empty())
                    res += (min(h[st.top()], h[i]) - cur) * (i - st.top() -1);
            }
            st.push(i);
            
        }
        return res;
    }
};