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

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]

输出: 6

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/trapping-rain-water

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的解

  1. class Solution {
  2.     public int trap(int[] height) {
  3.         int len = height.length;
  4.         if(len < 3) return 0;
  5.         int left = 0;
  6.         int right = 1;
  7.         int rain = 0;
  8.         LinkedList<Integer> list = new LinkedList<>();
  9.         list.addLast(0);
  10.         while(right < len){
  11.             if(height[right] >= height[left]){
  12.                 list.clear();
  13.                 list.addLast(right);
  14.                 left = right;
  15.             }else{
  16.                 rain += height[left] - height[right];
  17.                 //int last = list.getLast();
  18.                 while(height[right] >= height[list.getLast()]) list.removeLast();// last不是连续的
  19.                 list.addLast(right);
  20.             }
  21.             right++;
  22.         }
  23.         if(list.size() > 1){
  24.             int first = list.removeFirst();
  25.             int last = first;
  26.             for(int sec : list){
  27.                 rain -= (height[first] - height[sec]) * (sec - last);
  28.                 last = sec;
  29.             }
  30.         }
  31.         return rain;
  32.     }
  33. }

栈

  1. public int trap(int[] height) {
  2.     int ans = 0, current = 0;
  3.     Deque<Integer> stack = new LinkedList<Integer>();
  4.     while (current < height.length) {
  5.         while (!stack.isEmpty() && height[current] > height[stack.peek()]) {
  6.             int top = stack.pop();
  7.             if (stack.isEmpty())
  8.                 break;
  9.             int distance = current - stack.peek() - 1;
  10.             int bounded_height = Math.min(height[current], height[stack.peek()]) - height[top];
  11.             ans += distance * bounded_height;
  12.         }
  13.         stack.push(current++);
  14.     }
  15.     return ans;
  16. }
  18. 作者：LeetCode
  19. 链接：https://leetcode-cn.com/problems/trapping-rain-water/solution/jie-yu-shui-by-leetcode/
  20. 来源：力扣（LeetCode）
  21. 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。