建立网站心得,大连领超科技网站建设有限公司,系统开发费用账务处理,wordpress怎么防爬虫给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。
方法一#xff1a;双指针法
思路
使用两个指针 left 和 right 分别指向数组的两端#xff0c;同时记录左边的最大高度 leftMax 和右边的最大高度 rig…给定 n 个非负整数表示每个宽度为 1 的柱子的高度图计算按此排列的柱子下雨之后能接多少雨水。
方法一双指针法
思路
使用两个指针 left 和 right 分别指向数组的两端同时记录左边的最大高度 leftMax 和右边的最大高度 rightMax。在每次迭代中比较 left 和 right 指向的高度选择较小的一端进行处理。如果 height[left] height[right]则说明左边的柱子可能会接到雨水此时计算当前位置能接到的雨水量leftMax - height[left]并将 left 指针右移一位否则说明右边的柱子可能会接到雨水计算当前位置能接到的雨水量rightMax - height[right]并将 right 指针左移一位。重复这个过程直到 left 和 right 指针相遇。
代码实现
function trap(height: number[]): number {let left 0;let right height.length - 1;let leftMax 0;let rightMax 0;let result 0;while (left right) {if (height[left] height[right]) {leftMax Math.max(leftMax, height[left]);result leftMax - height[left];left;} else {rightMax Math.max(rightMax, height[right]);result rightMax - height[right];right--;}}return result;
}// 示例调用
const height [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const rainWater trap(height);
console.log(下雨之后能接的雨水:, rainWater);复杂度分析
时间复杂度(O(n))其中 n 是数组 height 的长度。因为只需要遍历一次数组。空间复杂度(O(1))只使用了常数级的额外空间。
方法二单调栈法
思路
使用一个单调栈来存储柱子的索引。遍历数组对于每个柱子如果当前柱子的高度大于栈顶柱子的高度则说明栈顶柱子可以接到雨水计算并累加接水量然后将栈顶元素出栈重复这个过程直到栈为空或者当前柱子的高度不大于栈顶柱子的高度。最后将当前柱子的索引入栈。
代码实现
function trap(height: number[]): number {const stack: number[] [];let result 0;for (let i 0; i height.length; i) {while (stack.length 0 height[i] height[stack[stack.length - 1]]) {const top stack.pop();if (stack.length 0) {break;}const distance i - stack[stack.length - 1] - 1;const minHeight Math.min(height[i], height[stack[stack.length - 1]]) - height[top];result distance * minHeight;}stack.push(i);}return result;
}// 示例调用
const height2 [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1];
const rainWater2 trap(height2);
console.log(下雨之后能接的雨水:, rainWater2);复杂度分析
时间复杂度(O(n))其中 n 是数组 height 的长度。虽然有一个嵌套的 while 循环但每个元素最多入栈和出栈一次所以总的时间复杂度仍然是 (O(n))。空间复杂度(O(n))在最坏情况下栈中可能会存储所有的柱子索引。
综上所述双指针法和单调栈法都能有效地解决接雨水问题双指针法的代码相对简单空间复杂度较低单调栈法的思路相对复杂一些但也能清晰地处理接雨水的逻辑。
