image.png

双指针

在暴力解法的核心主要是查找出左右两边的最大值，但是我们仔细分析会发现，只要 right_max[i] > left_max[i]，柱子i位置的最大存水量就由left_max决定；反之如果 left_max[i] > right_max[i]，则由right_max决定。
根据这个思路，我们还是先从左往右扫描数组，我们可以认为如果一侧有更高的柱子（例如右侧），积水的高度依赖于当前方向的高度（从左到右）。当我们发现另一侧（右侧）的条形块高度不是最高的，我们则开始从相反的方向遍历（从右到左）。
此时我们维护左右两个指针，通过两个指针交替进行遍历，实现一次遍历完成。
对于位置left而言，它左边的最大值一定是left_max，右边的最大值大于等于right_max。如果此时left_max < right_max，那么它就能计算出它的位置能存多少水，无论右边将来会不会出现更大的值，都不影响计算出的结果，所以当height[left] < height[right] 时，我们去处理left指针。反之，我们去处理right指针。

  1. var trap = function(height) {
  2.     let sum = 0;
  3.     let left_max = 0;
  4.     let right_max = 0;
  5.     let left = 0;
  6.     let right = height.length - 1;
  7.     while(left < right) {
  8.         if (height[left] < height[right]) {
  9.             left_max = Math.max(left_max, height[left]);
  10.             sum += left_max - height[left];
  11.             left++;
  12.         } else {
  13.             right_max = Math.max(right_max, height[right]);
  14.             sum += right_max - height[right];
  15.             right--;
  16.         }
  17.     }
  18.     return sum;
  19. };
  1. // 单调栈
  2. var trap = function(height) {
  3.     let ans = 0;
  4.     let left = 0, right = height.length - 1;
  5.     let leftMax = 0, rightMax = 0;
  6.     while (left < right) {
  7.         leftMax = Math.max(leftMax, height[left]);
  8.         rightMax = Math.max(rightMax, height[right]);
  9.         if (height[left] < height[right]) {
  10.             ans += leftMax - height[left];
  11.             ++left;
  12.         } else {
  13.             ans += rightMax - height[right];
  14.             --right;
  15.         }
  16.     }
  17.     return ans;
  18. };
  1. var trap = function(height) {
  2.     let ans = 0;
  3.     const stack = [];
  4.     const n = height.length;
  5.     for (let i = 0; i < n; ++i) {
  6.         while (stack.length && height[i] > height[stack[stack.length - 1]]) {
  7.             const top = stack.pop();
  8.             if (!stack.length) {
  9.                 break;
  10.             }
  11.             const left = stack[stack.length - 1];
  12.             const currWidth = i - left - 1;
  13.             const currHeight = Math.min(height[left], height[i]) - height[top];
  14.             ans += currWidth * currHeight;
  15.         }
  16.         stack.push(i);
  17.     }
  18.     return ans;
  19. };
  21. 作者：LeetCode-Solution
  22. 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode-solution-tuvc/
  23. 来源：力扣（LeetCode）
  24. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。