ByteDance真题 2020-06-29 42. Trapp

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

My solution / AC

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let result = 0;
    for(let i=0; i<height.length; i++){
        let lmax=0, rmax=0;
        for(let j=0; j<i; j++){
            if(height[j]>lmax){
                lmax = height[j];
            }
        }
        for(let j=i+1; j<height.length; j++){
            if(height[j]>rmax){
                rmax = height[j];
            }
        }
        let water = Math.min(lmax, rmax) - height[i];
        result += water>0 ? water : 0;
    }
    return result;
};

Better Solution / AC

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let res=0;
    let left=0, right=height.length-1;
    let lmax=height[left], rmax=height[right];
    while(left<=right){
        if(lmax<=rmax) {
          if(height[left]>=lmax) lmax = height[left];
          else {
              res += lmax-height[left];
          }
          left++;
        } else {
            if(height[right]>=rmax) rmax = height[right];
            else {
                res += rmax-height[right];
            }
            right--;
        }
    }
    return res;
};

https://leetcode.com/problems/trapping-rain-water/discuss/17357/Sharing-my-simple-c%2B%2B-code%3A-O(n)-time-O(1)-space
这种写法能够减少循环，节省了运算时间。

通过两个指针分别向中间靠近，左边低流左边的，右边低流右边的。因为到了中间必然会有两者的交汇，因此必须要left<=right来作为结束循环的条件（而不能用left<right，因为两者相等时还有最后一个left==right那一竖没有流的）。