辽宁企业网站建设,3a汽车集团公司网络营销方案,网页设计与网站建设在线作业,安徽网站建设流程题目介绍
给定 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…题目介绍
给定 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
解答
C解法
class Solution {
public:int trap(vectorint height) {// 双指针 前后最大值// 每个位置左边和右边最高高度分别记录在数组上// 每个位置可以储水的容量取决于其左右两边最大值之小者if(height.size() 2) return 0;vectorint maxLeft(height.size(), 0);vectorint maxRight(height.size(), 0);int size maxRight.size();// 记录每个柱子左边的最大高度maxLeft[0] height[0];for(int i 1; i size; i){maxLeft[i] max(maxLeft[i - 1], height[i]);}maxRight[size - 1] height[size - 1];for(int i size - 2; i 0; --i){maxRight[i] max(maxRight[i 1], height[i]);}int res 0;for(int i 1; i size; i){res min(maxRight[i], maxLeft[i]) - height[i];}return res;}
};python3
class Solution:# 每一个位置能盛放多少水取决于其左边和右边柱子的最大高度的小者def trap(self, height: List[int]) - int:n len(height)# pre_max[i] 表示下标为i的柱子前面(包括下标为i的柱子)的最大高度pre_max [0] * npre_max[0] height[0] for i in range(1, n):pre_max[i] max(pre_max[i - 1], height[i])# suf_max[i] 表示下标为i的柱子(包括下标为i的柱子)后面的最大高度suf_max [0] * nsuf_max[-1] height[-1]#n-2 ~ 0 for i in range(n - 2, -1, -1):suf_max[i] max(suf_max[i 1], height[i])ans 0# zip 将其中的列表打包成元组的列表用来迭代for h, pre, suf in zip(height, pre_max, suf_max):ans min(pre, suf) - hreturn ans
