LeetCode42. 接雨水 Bertha 。 2022-09-08 10:30 116阅读 0赞 难度:困难 题目描述: > 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 示例 1: ![在这里插入图片描述][c0121c2638074146a76f060701d9b3f4.png] 输入: > 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 取决于左右边矮的那个 class Solution { public: int trap(vector<int>& height) { int n = height.size(); if(n==0){ return 0; } vector<int> left(n,0); vector<int>right(n,0); int ans = 0; left[0] = height[0]; for(int i=1;i<n;i++){ left[i] = max(height[i],left[i-1]); } right[n-1] = height[n-1]; for(int i = n-2; i >= 0; i--){ right[i] = max(height[i],right[i+1]); } for(int i=0;i<n;i++){ ans+=min(left[i]-height[i],right[i]-height[i]); } return ans; } }; [c0121c2638074146a76f060701d9b3f4.png]: /images/20220829/af96d5df6ecc45fa80af8c73a01baa5c.png
还没有评论,来说两句吧...