描述

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

示例

示例1：
rainwatertrap.png

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

示例2：

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

提示

  • n == height.length
  • 0 <= n <= 3 * 104
  • 0 <= height[i] <= 105


解题思路

官方题解

  • 维护一个单调递减栈
  • 如果栈为空或者当前高度小于栈顶高度，压栈
  • 如果大于栈顶高度，将栈顶元素出栈，计算积水值，直到栈空或者当前元素小于栈顶。

    代码

    class Solution {
  public int trap(int[] height) {
      int n = height.length;
      if (n == 0) return 0;
      int sum = 0;
      Deque<Integer> deque = new LinkedList<Integer>();
      for (int i = 0; i < n; i++) {
          while (!deque.isEmpty() && height[i] >= height[deque.peekLast()]) {
              int last = height[deque.peekLast()];
              deque.pollLast();
              if (deque.isEmpty()) {
                  break;
              }
              sum += (Math.min(height[i], height[deque.peekLast()]) - last) * (i - deque.peekLast() - 1);
          }
          deque.addLast(i);
      }
      return sum;
  }
}

复杂度分析

时间复杂度：O(n)，其中 n 是数组 height 的长度。从 0 到 n−1 的每个下标最多只会入栈和出栈各一次。

空间复杂度：O(n)，其中 n 是数组 height 的长度。空间复杂度主要取决于栈空间，栈的大小不会超过 n。