郴州买房网站,浙江公司网站建设制作,erp是什么办公软件,公众号小程序制作平台LeetCode 42. 接雨水
题目描述
给定一个非负整数数组 height 表示柱状图中每个柱子的高度#xff0c;请你计算按此排列的柱状图能接多少雨水。
示例 1#xff1a;
输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释#xff1a;上面的柱状图可以…LeetCode 42. 接雨水
题目描述
给定一个非负整数数组 height 表示柱状图中每个柱子的高度请你计算按此排列的柱状图能接多少雨水。
示例 1
输入height [0,1,0,2,1,0,1,3,2,1,2,1]
输出6
解释上面的柱状图可以通过 6 个单位的雨水。示例 2
输入height [4,2,0,3,2,5]
输出9提示
0 height.length 10^40 height[i] 10^5
Java 实现解法
方法一动态规划
class Solution {public int trap(int[] height) {if (height null || height.length 0) {return 0;}int n height.length;int[] leftMax new int[n];int[] rightMax new int[n];leftMax[0] height[0];for (int i 1; i n; i) {leftMax[i] Math.max(leftMax[i - 1], height[i]);}rightMax[n - 1] height[n - 1];for (int i n - 2; i 0; i--) {rightMax[i] Math.max(rightMax[i 1], height[i]);}int water 0;for (int i 0; i n; i) {water Math.min(leftMax[i], rightMax[i]) - height[i];}return water;}
}解题思路
动态规划这个问题可以通过两次遍历数组来解决。首先我们从左到右遍历数组记录每个位置左侧最高的柱子高度。然后从右到左遍历数组记录每个位置右侧最高的柱子高度。计算雨水量对于数组中的每个柱子能接到的雨水量取决于其左右两侧最高的柱子高度中的较小值减去该柱子的高度。这样每个柱子能接到的雨水量就是 min(leftMax[i], rightMax[i]) - height[i]。累加雨水量遍历整个数组将每个柱子能接到的雨水量累加起来就得到了总的雨水量。
这种方法的时间复杂度是 O(n)其中 n 是数组 height 的长度因为我们对数组进行了三次遍历。空间复杂度是 O(n)因为我们使用了两个额外的数组 leftMax 和 rightMax 来存储左右两侧的最高柱子高度。
方法二双指针
class Solution {public int trap(int[] height) {int n height.length;int left 0, right n - 1;int leftMax 0, rightMax 0;int water 0;while (left right) {if (height[left] height[right]) {if (height[left] leftMax) {leftMax height[left];} else {water leftMax - height[left];}left;} else {if (height[right] rightMax) {rightMax height[right];} else {water rightMax - height[right];}right--;}}return water;}
}解题思路
双指针我们使用两个指针 left 和 right 分别从数组的两端开始向中间移动。维护最大高度同时维护两个变量 leftMax 和 rightMax 来记录 left 和 right 指针左侧和右侧的最大高度。计算雨水量当 height[left] height[right] 时我们移动 left 指针并更新 leftMax。如果 height[left] 小于 leftMax则这部分可以接到雨水雨水量为 leftMax - height[left]。类似地当 height[left] height[right] 时我们移动 right 指针并更新 rightMax计算雨水量。累加雨水量将每次计算得到的雨水量累加起来得到总的雨水量。
这种方法的时间复杂度是 O(n)其中 n 是数组 height 的长度因为我们只遍历了数组一次。空间复杂度是 O(1)因为我们只使用了常数个额外的变量没有使用额外的空间。
注来源leetcode网站
