本文共 3336 字，大约阅读时间需要 11 分钟。

题目

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.

Example:

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

Output: 6

我的想法

分层？但是这样复杂度太高了

解答

leetcode solution 1: Brute Force

第一步，计算左边的最高高度(包括当前位置) 第二步，计算右边的最高高度(包括当前位置) 第三步，储水量取决于左右两边高度中较低值与当前高度的差值

int trap(vector
   
    & 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--) {
    //Search the left part for max bar size            max_left = max(max_left, height[j]);        }        for (int j = i; j < size; j++) {
    //Search the right part for max bar size            max_right = max(max_right, height[j]);        }        ans += min(max_left, max_right) - height[i];    }    return ans;}
   

leetcode solution 2: Dynamic Programming

第一步，从左边计算每个位置的最高高度 第二步，从右边计算每个位置的最高高度 第三步，储水量等于前两步重叠部分的高度(即取较小值)减去当前位置的高度

核心思想：用数组将最高位置记录下来，避免了solution1中大量的重复计算

class Solution {
       public int trap(int[] height) {
           if(height == null || height.length<3) return 0;                int ans = 0;        int[] max_left = new int[height.length];        int[] max_right = new int[height.length];                max_left[0] = height[0];        max_right[height.length-1] = height[height.length-1];                for(int i = 1; i < height.length; i++){
               max_left[i] = Math.max(max_left[i-1], height[i]);        }        for(int i = height.length - 2; i > 0; i--){
               max_right[i] = Math.max(max_right[i+1], height[i]);        }                for(int i = 1; i < height.length - 1; i++){
               ans += Math.min(max_right[i], max_left[i]) - height[i];        }        return ans;    }}

leetcode solution 3: Using stacks

如果当前高度小于栈顶高度，入栈 否则，pop出栈顶(能蓄水的部分) 新栈顶与当前高度的较小值减去pop出的栈顶高度，为蓄水高度 循环，直到栈空或者当前高度小于栈顶高度

涉及到局部求解的问题可以考虑stack

class Solution {
       public int trap(int[] height) {
           int ans = 0, current = 0;        Stack
   
     st = new Stack<>();        while (current < height.length) {
               while (!st.empty() && height[current] > height[st.peek()]) {
                   int top = st.pop();                if (st.empty())                    break;                int distance = current - st.peek() - 1;                int bounded_height = Math.min(height[current], height[st.peek()]) - height[top];                ans += distance * bounded_height;            }            st.push(current++);        }        return ans;    }}
   

leetcode solution 4: Using 2 pointers

性能最佳！！！

class Solution {
       public int trap(int[] height) {
           int left = 0, right = height.length - 1;        int ans = 0;        int left_max = 0, right_max = 0;        while (left < right) {
               if (height[left] < height[right]) {
                   left_max = Math.max(height[left], left_max);                ans += (left_max - height[left]);                ++left;            }            else {
                   right_max = Math.max(height[right], right_max);                ans += (right_max - height[right]);                --right;            }        }        return ans;    }}

转载地址：http://kbqvb.baihongyu.com/