Trapping Rain Water

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

Givennnon-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.

For example, Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.

Thoughts

一维数组每个元素代表高度，往里头灌水问最多能蓄多少。可以观察到，一个位置能蓄多少水是由该位置左右最高的块的最小值（再减去当前位置的块高度）决定的。比如4号位置，它能蓄2点水是因为2号位置的高是2，6号位置的高比2还大。因此分别计算每个位置的左，右最高块高度值是多少。让它们相减再减去当前块的高度即所求。

Code

class Solution {
    public int trap(int[] height) {
        if (height.length <= 2) {
            return 0;
        }
        int[] lH = new int[height.length];
        int[] rH = new int[height.length];

        for (int i = 1; i < height.length; i++) {
            lH[i] = Math.max(lH[i - 1], height[i - 1]);
        }

        for (int i = height.length - 2; i >= 0; i--) {
            rH[i] = Math.max(height[i + 1], rH[i + 1]); 
        }

        int sum = 0;
        for (int i = 0; i < height.length; i++) {
            sum += Math.max(0, Math.min(lH[i], rH[i]) - height[i]); 
        }

        return sum;
    }
}

Analysis

时空复杂度都是O(N).

Ver.2

[l, r]看作当前问题的范围, 无需对max小的l遍历所有的r，因为r往前移会受限于l_max，遍历无意义。反之同理。

/*
 * @lc app=leetcode id=42 lang=cpp
 *
 * [42] Trapping Rain Water
 */

// @lc code=start
class Solution {
public:
    int trap(vector<int>& height) {
        int l = 0, r = height.size() - 1, lm = 0, rm = 0, res = 0;
        while (l < r) {
            lm = max(lm, height[l]);
            rm = max(rm, height[r]);
            if (lm < rm) res += lm - height[l++];
            else res += rm - height[r--];
        }
        return res;
    }
};
// @lc code=end