给定n个非负整数表示每个宽度为1的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。示例 1输入height [0,1,0,2,1,0,1,3,2,1,2,1]输出6解释上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图在这种情况下可以接 6 个单位的雨水蓝色部分表示雨水。示例 2输入height [4,2,0,3,2,5]输出9提示n height.length1 n 2 * 1040 height[i] 105动态规划class Solution { public int trap(int[] height) { int len height.length; // 如果数组长度为0返回0 if(len 0){ return 0; } // 创建一个数组用于存储每个位置左侧的最大高度 int[] leftMax new int[len]; for(int i 1; i len; i){ // 更新当前点的左侧最大高度 leftMax[i] Math.max(height[i-1], height[i]); } // 创建一个数组用于存储每个位置右侧的最大高度 int[] rightMax new int[len]; for(int i len-2; i 0; i--){ // 更新当前点的右侧最大高度 rightMax[i] Math.max(height[i], height[i1]); } int ans 0; // 计算每个位置能够存储的水量 for(int i 0; i len; i){ ans Math.min(leftMax[i], rightMax[i]) - height[i]; } // 返回能够存储的总水量 return ans; } }单调栈解决import java.util.Stack; class Solution { public int trap(int[] height) { // 初始化总雨水量为0 int totalWater 0; // 创建一个栈用于存储数组索引 StackInteger stack new Stack(); // 遍历每个高度 for (int i 0; i height.length; i) { // 当栈非空且当前高度大于栈顶所指的高度时 while (!stack.isEmpty() height[i] height[stack.peek()]) { // 取出栈顶的高度索引 int top stack.pop(); // 如果栈为空跳出循环 if (stack.isEmpty()) { break; } // 计算当前柱子的宽度 int distance i - stack.peek() - 1; // 计算能形成的水位高度差 int boundedHeight Math.min(height[i], height[stack.peek()]) - height[top]; // 计算当前能积的水量并加到总水量中 totalWater distance * boundedHeight; } // 将当前索引入栈 stack.push(i); } // 返回总雨水量 return totalWater; } }工作原理单调递减栈栈中存储的是高度数组的索引。栈内元素对应的高度从栈底到栈顶是非递增的。遍历高度数组对于每一个高度若其大于栈顶元素所指的高度即找到一个可能的凹槽则计算当前凹槽的水量。水量计算宽度凹槽宽度为当前索引i与栈顶下一个元素的索引之差再减去 1。高度水位高度差为min(当前高度, 栈顶下一个高度) - 栈顶高度。累加水量将计算出的水量累加到总水量中。在计算接雨水的过程中水的高度取决于柱子之间的最低高度。具体来说水只能被较矮的柱子挡住。因此关键在于找到最低的柱子并根据它来计算可能存储的水量。class Solution { public int trap(int[] height) { int lenheight.length; int left0,rightlen-1; int leftMax0,rightMax0; int ans0; while(leftright){ leftMaxMath.max(leftMax,height[left]); rightMaxMath.max(rightMax,height[right]); if(height[left]height[right]){ ansleftMax-height[left]; left; }else{ ans rightMax-height[right]; right--; } } return ans; } }判断逻辑水量计算基础对于height[left] height[right]的情况由于leftMax是从左侧移动过程中遇到的最大高度而rightMax是从右侧移动过程中遇到的最大高度因此当前柱子height[left]左侧的最大高度leftMax是可靠的。但是右侧的最大高度rightMax还可能会更新。因此此时计算left位置的积水量是安全的。为什么选择较小的高度如果height[left] height[right]意味着在当前位置left其右侧有更高的柱子。这个较高的柱子可以帮助挡住雨水。因此可以确定leftMax是最小的限制条件用它来计算当前位置可能存储的水量是安全的。如果height[left] height[right]那么右侧柱子在此时成为决定因素左侧的leftMax没有影响应该通过rightMax计算右侧的水量。例子说明假设height[left] 2height[right] 5当left侧低于right侧可以确定在左侧left柱子能容纳的水量只取决于leftMax。因此将left向右移动并计算leftMax - height[left]。如果反过来如果左侧高于或等于右侧则右侧可能会积水因此移动right向左并计算rightMax - height[right]。总结这一判断的核心在于小于左侧可能有积水计算左侧。大于等于右侧可能有积水计算右侧。初始状态下的right指针right指针初始位置它从数组的最右端开始。left指针初始位置它从数组的最左端开始。初始比较height[left] height[right]在算法的开始阶段我们用height[left] height[right]来判断接下来的行动。虽然right一开始位于数组的最右边但这并不影响算法的正确性原因如下rightMax的初始化初始时rightMax会等于height[right]。因为right指针在最右端所以rightMax一开始就是数组最右边的那个高度。随着right指针向左移动rightMax会逐渐更新为更大的值直到遍历完所有右边的柱子。初始状态的判断在开始时算法将left和right的柱子高度进行比较。如果height[left] height[right]说明左边的柱子比右边矮。在这种情况下右边更高的柱子可以“挡住”水因此左边柱子上方可能会有积水这时候左边的积水高度是可以确定的所以移动left指针并计算水量。如果height[left] height[right]算法会移动right指针。此时不会计算left指针位置的积水而是继续查看右边的柱子是否可能形成积水。意义在于确定安全的水量通过比较height[left]和height[right]算法确保了在当前位置计算水量时有足够的信息保证水量是准确的。rightMax和leftMax在算法执行过程中不断更新确保算法总是在安全的条件下进行计算。实际意义即使right指针最开始位于最右边这个初始比较也有意义因为它为整个算法奠定了基础。我们可以通过这个初始比较确保在移动left或right指针时计算的积水量是正确且安全的。举个例子假设height数组为[1, 0, 2, 1, 0, 1, 3]left和right初始分别在位置0和6left开始为1right开始为3。第一次比较时height[left] 1height[right] 3显然1 3我们可以放心地移动left指针因为左边的积水高度确定不会超过leftMax。总之这一步比较对于算法的正确性和水量计算至关重要即使right指针最初处于最右边也依然有效且必要。
