42. Trapping Rain Water

Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.

The above elevation map 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. Thanks Marcos for contributing this image!

Example:

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6

先用一個dp array從左掃到右紀錄左邊的最大高度，再從右掃到左紀錄右邊最大高度並且和dp array裡面已經存的左邊最大高度比較，取兩者之中較小的來當作儲水高度。

// Dynamic programming
int trap(vector<int>& height) { // time: O(n); space: O(n)
    int res = 0, mx = 0, n = height.size();
    vector<int> dp(n, 0);
    // scan from left to right to record max left height
    for (int i = 0; i < n; ++i) {
        dp[i] = mx;
        mx = max(mx, height[i]);
    }
    // reset mx to 0
    mx = 0;
    // scan from right to left to calculate res
    for (int i = n - 1; i >= 0; --i) {
        dp[i] = min(dp[i], mx); // record the minimum value between maxL and maxR
        mx = max(mx, height[i]);
        if (dp[i] > height[i]) res += dp[i] - height[i];
    }
    return res;
}

利用two pointers指向左右邊界，然後另外紀錄當前遇到過左右邊的最大值，maxL和maxR。比較左右邊界，移動高度小的那一個，如果是左邊較矮，那麼比較當前的左邊界高度和目前記錄到的左邊高度最大值，如果當前高度小於左邊高度最大值，代表可以儲水，不是的話則更新左邊高度最大值到當前的高度。反之，右邊也是一樣概念。

// Two pointers
int trap(vector<int>& height) { // time: O(n); space: O(1)
    int n = height.size(), l = 0, r = n - 1, maxL = 0, maxR = 0, res = 0;
    while (l < r) {
        if (height[l] <= height[r]) {
            if (height[l] >= maxL) maxL = height[l];
            else res += maxL - height[l];
            ++l;
        } else {
            if (height[r] >= maxR) maxR = height[r];
            else res += maxR - height[r];
            --r;
        }
    }
    return res;
}

利用monotonic stack來儲存高度遞減的index，如果遇到高度大於stack的top，則開始計算當前能儲的水量。

// Monotonic Stack
int trap(vector<int>& height) { // time: O(n); space: O(n)
    int res = 0, i = 0, n = height.size();
    stack<int> st;
    while (i < n) {
        if (st.empty() || height[i] <= height[st.top()]) st.push(i++);
        else {
            int t = st.top(); st.pop();
            if (st.empty()) continue;
            res += (min(height[st.top()], height[i]) - height[t]) * (i - st.top() - 1);
        }
    }
    return res;
}

11. Container With Most Water