网站seo外链,网站备案 换空间,中国建设银行个人网上银行登录官网,WordPress自动推送到公众号42. 接雨水 题目#xff1a;
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图#xff0c;计算按此排列的柱子#xff0c;下雨之后能接多少雨水。 示例 1#xff1a; 输入#xff1a;height [0,1,0,2,1,0,1,3,2,1,2,1]
输出#xff1a;6
解释#xff1a;上面是由数组…
42. 接雨水 题目
给定 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 * 0 height[i] 思路
首先获取数组长度。
其次获取每一个点的左侧和右侧的最大高度。
最后找到每一个点左侧和右侧最大高度较小的那个因为只有较小的那个高度才能限制雨水容量。将这个减去该位置的高度即可得到该位置的雨水单位数将其累加到最终结果中。 代码
class Solution {
public:int trap(vectorint height) {int n height.size();if (n 0) {return 0;}vectorint leftMax(n);leftMax[0] height[0];for (int i 1; i n; i) {leftMax[i] max(leftMax[i - 1], height[i]);//cout leftMax[i] |;}//cout endl;vectorint rightMax(n);rightMax[n - 1] height[n - 1];for (int i n - 2; i 0; --i) {rightMax[i] max(rightMax[i 1], height[i]);//cout rightMax[i] |;}//cout endl;int ans 0;for (int i 0; i n; i) {ans min(leftMax[i], rightMax[i]) - height[i];//cout min(leftMax[i], rightMax[i]) - height[i] |;}return ans;}
};
