小游戏网站网址,贵阳设计工作室,网站建设开发程序代码,wordpress 高端给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释#xff1a;上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表…给定 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返回0if(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) {// 初始化总雨水量为0int 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 和 6
left 开始为 1right 开始为 3。第一次比较时height[left] 1height[right] 3显然 1 3我们可以放心地移动 left 指针因为左边的积水高度确定不会超过 leftMax。
总之这一步比较对于算法的正确性和水量计算至关重要即使 right 指针最初处于最右边也依然有效且必要。
