力扣热门100题之接雨水【困难】-Toy模板网

这篇具有很好参考价值的文章主要介绍了力扣热门100题之接雨水【困难】。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

题目描述

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

示例 1：

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

示例 2：

输入：height = [4,2,0,3,2,5]
输出：9

提示：

力扣热门100题之接雨水【困难】,LeetCode力扣,leetcode,算法,职场和发展

解法1 按列计算

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let area=0;
    let leftMax=0;
    let rightMax=0;
    for(let i=0;i<height.length;i++){
          rightMax=findRightMax(leftMax,i,height);
         if(height[i]<leftMax&&rightMax>height[i]){
             area+=Math.min(leftMax,rightMax)-height[i];
         }
         else if(!findRightMax(leftMax,i,height)){
             leftMax=height[i];
         }
         if(height[i]>leftMax) leftMax=height[i];
    }
    return area;
};
function findRightMax(num,j,height){
    let n=0;
    for(let i=j;i<height.length;i++){
        if(height[i]>=num){
            return height[i];
        }
        if(height[i]>n)n=height[i]
    }
    return n;
}

执行结果：
力扣热门100题之接雨水【困难】,LeetCode力扣,leetcode,算法,职场和发展
解法2：双指针解法【注意理解】

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
   let area=0;
   if(height.length<=1) return 0;
   let left=0;
   let leftMax=0;
   let right=height.length-1;
   let rightMax=0;
   while(left<right){
       leftMax=Math.max(leftMax,height[left]);
       rightMax=Math.max(rightMax,height[right]);
       if(height[left]<height[right]){
           area+=leftMax-height[left];
           left++;
       }else{
           area+=rightMax-height[right];
           right--;
       }
    
   }
   return area;
};

执行情况：
力扣热门100题之接雨水【困难】,LeetCode力扣,leetcode,算法,职场和发展
解法3：单调栈【参照力扣官方】

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
   let area=0;
   if(height.length<=1) return 0;
   const stack=[]//存值值单调递减的下标
   for(let i=0;i<height.length;i++){
       while(stack.length&&height[i]>height[stack[stack.length-1]]){
           let top=stack.pop();
           if(stack.length==0){
               break;
           }
            const left = stack[stack.length - 1];
            const currWidth = i - left - 1;
            const currHeight = Math.min(height[left], height[i]) - height[top];
            area += currWidth * currHeight;
       }
       stack.push(i);
   }
   return area;
};