leetcode42：接雨水问题 #122

Activity

1. latte03 commented on Oct 30, 2020

   

   latte03

   on Oct 30, 2020

   More actions

   暴力解法

   // 获取最大高度
   function getMaxHeight(array) {
     let maxHeight = 0;
     array.forEach((element) => {
       if (element > maxHeight) maxHeight = element;
     });
     return maxHeight;
   }
   // 获取正数，可以设置默认值
   function getPositiveNumber(number, def) {
     return number < 0 ? (def ? def : 0) : number;
   }
   
   function trap(height) {
     if (lenght === 0) return 0;
   
     let total = 0;
   
     for (let i = 0; i < lenght; i++) {
       const leftMax = getMaxHeight(height.slice(0, i));
       const rightMax = getMaxHeight(height.slice(i + 1, lenght));
       total += getPositiveNumber(Math.min(leftMax, rightMax) - height[i]);
     }
     return total;
   }

   双指针

   function trap(height) {
     let total = 0;
     let left = 0,
       right = height.length - 1,
       leftMax = 0,
       rightMax = 0;
     while (left <= right) {
       leftMax = Math.max(leftMax, height[left]);
       rightMax = Math.max(rightMax, height[right]);
       if (leftMax < rightMax) {
         total += leftMax - height[left];
         left++;
       } else {
         total += rightMax - height[right];
         right--;
       }
     }
     return total;
   }

   👍React with 👍1Reacted by Wei Mingye
2. AnranS commented on Nov 18, 2020

   

   AnranS

   on Nov 18, 2020

   More actions

   栈

   var trap = function (height) {
       let stack = [];
       let index = 0;
       let sumArea = 0;
       while (index < height.length) {
           while (stack.length !== 0 && height[index] > height[stack[stack.length - 1]]) {
               let h = height[stack[stack.length - 1]];
               stack.pop();
               if (stack.length === 0) break;
               let w = index - stack[stack.length - 1] - 1;
               let min = Math.min(height[stack[stack.length - 1]], height[index]);
               sumArea += (min - h) * w;
           }
           stack.push(index);
           index++;
       }
       return sumArea;
   };
3. Forever17s commented on Feb 27, 2021

   

   Forever17s

   on Feb 27, 2021

   More actions

   双指针，中间向两边扩展

   var trap = function(height) {
     if(height.length <= 1) return 0;
   
     const getMax = (list) => {
         if (!list.length) return 
         let maxIndex = 0
         for(let i = 1; i < list.length; i ++) {
             if(list[i] > list[maxIndex]) maxIndex = i
         }
         return maxIndex
     }
   
     let maxLeft = maxRight = getMax(height);
     let sum = 0;
   
     while(maxLeft > 0) {
         let temp = getMax(height.slice(0, maxLeft))
         for(let i = temp; i < maxLeft; i ++){
             sum += height[temp] - height[i]
         }
         maxLeft = temp
     }
   
     while(maxRight < height.length - 1) {
         let temp = getMax(height.slice(maxRight + 1, height.length)) + maxRight + 1
         for(let i = maxRight + 1; i < temp; i ++){
             sum += height[temp] - height[i]
         }
         maxRight = temp
     }
   
     return sum
   };
4. lewisYe commented on Apr 8, 2021

   

   lewisYe

   on Apr 8, 2021

   Last edited by lewisYe

   More actions

   暴力

   var trap = function(height) {
       let len = height.length
       if(!len)return 0
       let sum = 0
       for(let i=0;i<len;i++){
           let leftA = []
           let leftB = []
           for(let n=0;n<i;n++){
               leftA.push(height[n])
           }
           for(let n=i+1;n<len;n++){
               leftB.push(height[n])
           }
           let leftMax = leftA.length ? Math.max.apply(null,leftA) : 0
           let rightMax = leftB.length ? Math.max.apply(null,leftB) : 0
            
           sum += Math.min(leftMax,rightMax) - height[i] > 0 ? Math.min(leftMax,rightMax) - height[i] : 0
       }
       return sum
   };
   

   这个leetcode 上超时了 优化一下如下

   var trap = function(height) {
       let len = height.length
       if(!len)return 0
       let sum = 0
       for(let i=0;i<len;i++){
           let leftA = []
           let leftB = []
           let leftMax= -1;
           let rightMax = -1
           for(let n=0;n<i;n++){
               if(height[n] > leftMax){
                   leftMax = height[n]
               }
           }
           for(let n=i+1;n<len;n++){
               if(height[n] > rightMax){
                   rightMax = height[n]
               }
           }
           sum += Math.min(leftMax,rightMax) - height[i] > 0 ? Math.min(leftMax,rightMax) - height[i] : 0
       }
       return sum
   };
   
5. JohnApache commented on Apr 28, 2021

   

   JohnApache

   on Apr 28, 2021

   More actions

   可能用的指针比较多，基本原理也是双指针，做了一个右边双指针为了补全左双指针无法覆盖到的位置，应该有优化的空间

   const trap = (height: number[]) => {
       const len = height.length;
       if (len <= 2) return 0;
       let slowLeftPos = 0;
       let fastLeftPos = 0;
       let slowRightPos = len - 1;
       let fastRightPos = len - 1;
       let result = 0;
       let currentTotalHeight = 0;
       while (fastLeftPos < len) {
           const slowLeftHeight = height[slowLeftPos];
           const fastLeftHeight = height[fastLeftPos];
           if (!slowLeftHeight) {
               slowLeftPos++;
               fastLeftPos++;
               continue;
           }
           if (slowLeftPos === fastLeftPos || slowLeftHeight > fastLeftHeight) {
               currentTotalHeight += fastLeftHeight;
               fastLeftPos++;
               continue;
           }
   
           result += (fastLeftPos - slowLeftPos) * slowLeftHeight - currentTotalHeight;
           slowLeftPos = fastLeftPos; // 移动左慢指针至左快指针位置
           currentTotalHeight = 0;
       }
   
       currentTotalHeight = 0; // 重制 currentTotalHeight
   
       while (fastRightPos >= slowLeftPos) {
           const slowRightHeight = height[slowRightPos];
           const fastRightHeight = height[fastRightPos];
           if (!slowRightHeight) {
               slowRightPos--;
               fastRightPos--;
               continue;
           }
           if (slowRightPos === fastRightPos || slowRightHeight > fastRightHeight) {
               currentTotalHeight += fastRightHeight;
               fastRightPos--;
               continue;
           }
   
           result += (slowRightPos - fastRightPos) * slowRightHeight - currentTotalHeight;
           slowRightPos = fastRightPos; // 移动右慢指针至右快指针位置
           currentTotalHeight = 0;
       }
   
       return result;
   };