网站建设网站推广服务公司,北京专业的网络seo,做公司网站的公,百度网站收入接雨水
给定 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,…接雨水
给定 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 实现思路
接雨水问题的实现思路主要基于以下观察 局部最大值一个柱子能接雨水的量取决于它左右两边最高的柱子高度中的较小值因为雨水只能在两者较低的一侧积累。 双指针使用两个指针 left 和 right 分别从数组的两端向中间遍历。这样可以同时考虑左右两边的柱子高度。 维护最大高度在遍历过程中维护两个变量 leftMax 和 rightMax 来记录从左边和右边开始遍历到目前为止遇到的最高的柱子高度。 计算雨水量当遍历到的柱子高度小于 leftMax 或 rightMax 时可以计算出当前柱子能接的雨水量即 min(leftMax, rightMax) - height[i]。如果柱子高度大于等于记录的最大高度则更新 leftMax 或 rightMax。 累加雨水量将每次计算出的雨水量累加到总雨水量 ans 中。 边界条件如果输入数组为空或长度为0则直接返回0因为没有柱子可以接雨水。
具体步骤如下 初始化两个指针 left 和 right 分别指向数组的开始和结束位置以及两个变量 leftMax 和 rightMax 为0。 使用一个循环当 left 小于 right 时继续执行 如果 height[left] height[right]则移动 left 指针并更新 leftMax 如果当前柱子高度大于等于 leftMax则更新 leftMax。否则计算当前柱子能接的雨水量并累加到 ans。否则移动 right 指针并更新 rightMax类似地更新 rightMax 和累加雨水量。 当 left 和 right 相遇时遍历结束返回计算出的总雨水量 ans。
这种双指针的方法时间复杂度为 O(n)其中 n 是数组 height 的长度因为每个元素只被遍历一次。空间复杂度为 O(1)因为只需要常数级别的额外空间。 思路模拟
让我们通过一个模拟来更深入地理解接雨水问题的解决思路。假设我们有以下高度数组
height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1]
我们的目标是找到这些柱子之间可以接多少雨水。下面是一步步的模拟过程 初始化两个指针 left 和 right 分别指向数组的两端即 left 0 和 right length - 1。同时初始化两个变量 leftMax 和 rightMax 来记录左右两边遍历过程中的最大高度初始值设为0。 遍历开始 当 left right 时执行循环。比较 height[left] 和 height[right] 如果 height[left] height[right]说明我们处于左侧的较低部分我们需要更新 leftMax 并可能计算左侧的雨水量。如果 height[left] height[right]我们处于右侧的较低部分或两边高度相同更新 rightMax 并可能计算右侧的雨水量。 在每一步中我们执行以下操作 如果当前柱子的高度小于 leftMax则当前柱子可以接到雨水雨水量为 leftMax - height[left]。如果当前柱子的高度大于或等于 leftMax则更新 leftMax 为当前柱子的高度。 同理对于右侧 如果 height[right] height[left]则 rightMax 可能更新并且可能计算右侧的雨水量。如果 height[right] 更新了 rightMax则不会立即计算雨水因为只有在移动到更矮的柱子时才会计算。 重复步骤3和4直到 left 和 right 相遇。 累加每一步计算的雨水量得到最终结果。
让我们模拟这个过程
初始状态left 0, right 12, leftMax 0, rightMax 0, ans 0移动 left 到下一个元素leftMax 更新为1height[1]。移动 right 到前一个元素rightMax 更新为1height[12]。继续移动 left 和 right更新 leftMax 和 rightMax直到它们指向相邻的元素。
下面是模拟的详细步骤
left: 0 1 2 3 4 5 6 7 8 9 10 11 12 (right) height: 0 1 0 2 1 0 1 3 2 1 2 1 0 leftMax: 0 1 1 2 2 2 3 3 3 2 2 1 1 rightMax: 0 0 0 0 1 1 1 2 3 3 2 1 1 ans: 0 0 0 2 3 4 4 5 6 6 5 4 3
在每一步我们可以看到 leftMax 和 rightMax 的更新以及计算的雨水量累加到 ans 中。最终ans 的值是6这就是我们可以接到的雨水总量。
请注意这个模拟是为了演示算法的逻辑流程实际的代码实现会使用条件语句来确定何时更新 leftMax、rightMax 以及何时计算雨水量。 实现代码
public int trap(int[] height) {if (height null || height.length 0) {return 0;}int n height.length;int left 0, right n - 1;int leftMax 0, rightMax 0;int ans 0;while (left right) {if (height[left] height[right]) {// 当左边的柱子高度小于右边的柱子高度if (height[left] leftMax) {// 更新左边的柱子能接的雨水量leftMax height[left];} else {// 计算当前柱子能接的雨水量并累加到总雨水量中ans leftMax - height[left];}left;} else {// 右边的柱子高度不小于左边的柱子高度if (height[right] rightMax) {// 更新右边的柱子能接的雨水量rightMax height[right];} else {// 计算当前柱子能接的雨水量并累加到总雨水量中ans rightMax - height[right];}right--;}}return ans;}
