leetcode热题HOT42. 接雨水

一、问题描述：

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

二、解题思路：

思路1：通过动态规划的预处理方式，分别计算每个柱子左右两侧的最大高度，然后通过遍历计算每个柱子的位置能够存储的水量，最终求得总的积水量。

代码示例：

public int trap(int[] height) {int length = height.length;if (length <= 2) return 0;int[] maxLeft = new int[length];int[] maxRight = new int[length];// 记录每个柱子左边柱子最大高度maxLeft[0] = height[0];for (int i = 1; i< length; i++) maxLeft[i] = Math.max(height[i], maxLeft[i-1]);// 记录每个柱子右边柱子最大高度maxRight[length - 1] = height[length - 1];for(int i = length - 2; i >= 0; i--) maxRight[i] = Math.max(height[i], maxRight[i+1]);// 求和int sum = 0;for (int i = 0; i < length; i++) {int count = Math.min(maxLeft[i], maxRight[i]) - height[i];if (count > 0) sum += count;}return sum;}

时间复杂度为 O(n)，空间复杂度为 O(n)，

思路2：用单调栈计算能接的雨水总量。

找到高-低-高形状的凹槽。
通过维护一个单调栈，单调栈存储的是下标，满足从栈底到栈顶的下标对应的数组 height 中的元素递减。
遍历数组，只要当前遍历的元素 height[i] 大于栈顶元素 height[top]，且栈中至少包含两个元素，就可以形成一个“凹槽”，height[i] 是右边界，top下面的元素是左边界 height[left] 。
凹槽的储水量 curheight = Math.min(height[left], height[i]) - height[top];

代码示例：

public int trap(int[] height) {int result = 0;  // 存储最终的接水量Deque<Integer> stack = new LinkedList<Integer>();  // 单调栈，存储数组索引int n = height.length;  // 数组长度for(int i = 0; i < n; ++i) {// 当栈非空且当前柱子高度大于栈顶柱子高度时，可以接雨水while(!stack.isEmpty() && height[i] > height[stack.peek()]) {int top = stack.pop();  // 弹出栈顶元素，表示当前可以接水的高度if(stack.isEmpty()) break;int left = stack.peek();  // 左边界，当前弹出元素的左边界int curwidth = i - left - 1;  // 当前可以接水的宽度// 当前可以接水的高度，即左右边界的最小高度减去当前弹出元素的高度int curheight = Math.min(height[left], height[i]) - height[top];// 累加当前可以接水的体积//System.out.println(i +" " + left + " " + top + " " + curwidth * curheight);result += curwidth * curheight;}stack.push(i);  // 将当前柱子索引压入栈中}  return result;  // 返回最终的接水量}