LeetCode 42. Trapping Rain Water

LeetCode 42. Trapping Rain Water

Description:

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.

Example:

Given [0,1,0,2,1,0,1,3,2,1,2,1], return 6.

---

解法一：暴力破解法

• 初始化ans = 0
• 从左到右遍历数组
• 初始化max_left = 0和max_right = 0
• 从当前元素遍历到起始元素，更新max_left = max(max_left, height[j])
• 从当前元素遍历到末尾元素，更新max_right = max(max_right, height[j])
• 将ans加上min(max_left, max_right) - height[i]

代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        int ans = 0;
        int size = height.size();
        for (int i = 1; i < size - 1; i++) {
            int max_left = 0, max_right = 0;
            for (int j = i; j >= 0; j--) {
                max_left = max(max_left, height[j]);// search the left part
            }
            for (int j = i; j < size; j++) {
                max_right = max(max_right, height[j]);// search the right part
            }
            ans += min(max_left, max_right) - height[i];
        }
        return ans;
    }
};

---

解法二：动态规划

• 找出从左到下标i的最大高度的元素left_max
• 找出从右到下标i的最大高度的元素right_max
• 遍历数组并更新ans：ans += min(left_max[i], right_max[i]) - height[i];

代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        if (height.size() == 0) return 0;
        int ans = 0;
        int size = height.size();
        vector<int> left_max(size), right_max(size);
        left_max[0] = height[0];
        for (int i = 1; i < size; i++) {
            left_max[i] = max(height[i], left_max[i - 1]);
        }
        right_max[size - 1] = height[size - 1];
        for (int i = size - 2; i >= 0; i--) {
            right_max[i] = max(height[i], right_max[i + 1]);
        }
        for (int i = 1; i < size - 1; i++) {
            ans += min(left_max[i], right_max[i]) - height[i];
        }
        return ans;
    }
};

---

解法三：利用left pointer和right pointer

• 初始化left pointer为0，right pointer为size-1
• 当left < right，循环：
  如果height[left]小于height[right]：
  如果height[left] >= left_max，更新left_max；否则将ans加上left_max - height[left]，且left++
  如果height[left]大于等于height[right]：
  如果height[right] >= right_max，更新left_max；否则将ans加上right_max - height[right]，且right--

代码如下：

class Solution {
public:
    int trap(vector<int>& height) {
        int left = 0, right = height.size() - 1;
        int ans = 0;
        int left_max = 0, right_max = 0;
        while (left < right) {
            if (height[left] < height[right]) {
                height[left] >= left_max ? (left_max = height[left]) : ans += (left_max - height[left]);
                ++left;
            }
            else {
                height[right] >= right_max ? (right_max = height[right]) : ans += (right_max - height[right]);
                --right;
            }
        }
        return ans;
    }
};