代码拉取完成,页面将自动刷新
同步操作将从 doocs/leetcode 强制同步,此操作会覆盖自 Fork 仓库以来所做的任何修改,且无法恢复!!!
确定后同步将在后台操作,完成时将刷新页面,请耐心等待。
给定 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.length
0 <= n <= 3 * 104
0 <= height[i] <= 105
动态规划法。
对于下标 i,水能达到的最大高度等于下标 i 左右两侧的最大高度的最小值,再减去 height[i]
就能得到当前柱子所能存的水量。
class Solution:
def trap(self, height: List[int]) -> int:
n = len(height)
if n < 3:
return 0
left_max = [height[0]] * n
for i in range(1, n):
left_max[i] = max(left_max[i - 1], height[i])
right_max = [height[n - 1]] * n
for i in range(n - 2, -1, -1):
right_max[i] = max(right_max[i + 1], height[i])
res = 0
for i in range(n):
res += min(left_max[i], right_max[i]) - height[i]
return res
class Solution {
public int trap(int[] height) {
int n;
if ((n = height.length) < 3) return 0;
int[] leftMax = new int[n];
leftMax[0] = height[0];
for (int i = 1; i < n; ++i) {
leftMax[i] = Math.max(leftMax[i - 1], height[i]);
}
int[] rightMax = new int[n];
rightMax[n - 1] = height[n - 1];
for (int i = n - 2; i >= 0; --i) {
rightMax[i] = Math.max(rightMax[i + 1], height[i]);
}
int res = 0;
for (int i = 0; i < n; ++i) {
res += Math.min(leftMax[i], rightMax[i]) - height[i];
}
return res;
}
}
此处可能存在不合适展示的内容,页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容,可点击提交进行申诉,我们将尽快为您处理。