给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。 输入: [0,1,0,2,1,0,1,3,2,1,2,1] 我们要求所能容纳的最多的雨水,那么我们只需要求每个柱子上方最多容纳多少,然后求和。一个柱子上面能容纳的雨水,取决于这个柱子两侧最高值(左x右y)的最小值,举个例子说,这个柱子高度为1,这个柱子左侧最高的那个柱子为4,右侧最高的那个柱子为3,那么这个柱子就可以容纳 min(3,4) -1 = 2个单位的雨水。 leetcode仅函数部分 完整代码
接雨水
题目描述
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)
输出: 6解题思路
代码如下
class Solution { public: int trap(vector<int>& height) { int ans = 0; for(int i = 0; i< height.size(); i++) { int a = i; int b = i; for(int j = i-1; j>=0; j--) { if(height[j]>height[a]) a = j; } for(int j = i+1; j< height.size(); j++) { if(height[j]>height[b]) b = j; } int x = min(height[a],height[b]) - height[i]; ans += x; } return ans; } };
#include<bits/stdc++.h> using namespace std; int main(){ int n; scanf("%d",&n); int a[110]; for(int i = 1; i<= n; i++){ scanf("%d",&a[i]); } a[0] = 0; a[n+1] = 0; int ans = 0; for(int i = 1; i<= n; i++){ int x = i; int y = i; for(int j = i-1; j>=0; j--){ if(a[j]>a[x]){ x = j; } } for(int j = i+1; j<=n+1; j++){ if(a[j]>a[y]){ y = j; } } int an = min(a[x],a[y])-a[i]; ans += max(an,0); } printf("%d",ans); }
本网页所有视频内容由 imoviebox边看边下-网页视频下载, iurlBox网页地址收藏管理器 下载并得到。
ImovieBox网页视频下载器 下载地址: ImovieBox网页视频下载器-最新版本下载
本文章由: imapbox邮箱云存储,邮箱网盘,ImageBox 图片批量下载器,网页图片批量下载专家,网页图片批量下载器,获取到文章图片,imoviebox网页视频批量下载器,下载视频内容,为您提供.
阅读和此文章类似的: 全球云计算