当前位置: 首页 > news >正文

LeetCode 42. 接雨水(Trapping Rain Water)

题目描述

 

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。 感谢 Marcos 贡献此图。

示例:

输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6

 

解题思路

 

基本思想是从数组首位置找到第一个大于其紧邻后面的数,将它作为第一个雨槽的左挡板,然后向后遍历找到第一个不小于它的的数作为右挡板,这两个高度之间即可构成一个容器,遍历中间的高度依次计算盛水单位,然后继续以此右挡板作为下一个雨槽的左挡板。如果没有找到不小于左挡板的高度,则把此段雨槽反过来重新按照之前的算法计算盛水容量。

 

代码

 

 1 class Solution {
 2 public:
 3     int trap(vector<int>& height) {
 4         int res = 0;
 5         if(height.size() < 3) return res;
 6         int left = 0;
 7         while(left < height.size() - 1 && height[left] <= height[left + 1])
 8             left++;
 9         if(left == height.size() - 1) return res;
10         int right = left + 1;
11         while(right < height.size()){
12             if(height[right] >= height[left]){
13                 for(int i = left + 1; i < right; i++)
14                     res += height[left] - height[i];
15                 left = right;
16                 right = left + 1;
17             }
18             else if(right == height.size() - 1){
19                 vector<int> hr;
20                 for(int i = right; i >= left; i--)
21                     hr.push_back(height[i]);
22                 res += trap(hr);
23                 break;
24             }
25             else right++;
26         }
27         return res;
28     }
29 };

 

转载于:https://www.cnblogs.com/wmx24/p/9556890.html

相关文章:

  • 多线程与单例模式
  • 我为什么要写博文?要写什么样的博文?
  • 要做一个什么样的人?
  • sklearn word2vec 实践
  • 遍历数组
  • html5特效库
  • Leetcode#344. Reverse String(反转字符串)
  • python3之os、sys
  • 经典类、新式类,网络编程
  • app和bootloader跳转 MSP与PSP
  • 最近的一些心态
  • flex 布局
  • Redis的概念及与MySQL的区别
  • 1078 字符串压缩与解压
  • Go 导入当前项目下的包
  • es6
  • golang 发送GET和POST示例
  • JavaSE小实践1:Java爬取斗图网站的所有表情包
  • JAVA多线程机制解析-volatilesynchronized
  • JAVA之继承和多态
  • SegmentFault 技术周刊 Vol.27 - Git 学习宝典:程序员走江湖必备
  • Spark VS Hadoop:两大大数据分析系统深度解读
  • VirtualBox 安装过程中出现 Running VMs found 错误的解决过程
  • 程序员该如何有效的找工作?
  • 机器学习学习笔记一
  • 聊聊springcloud的EurekaClientAutoConfiguration
  • 前端之Sass/Scss实战笔记
  • 如何使用Mybatis第三方插件--PageHelper实现分页操作
  • 设计模式(12)迭代器模式(讲解+应用)
  • 通信类
  • 小程序01:wepy框架整合iview webapp UI
  • 做一名精致的JavaScripter 01:JavaScript简介
  • ionic入门之数据绑定显示-1
  • 关于Kubernetes Dashboard漏洞CVE-2018-18264的修复公告
  • (Python) SOAP Web Service (HTTP POST)
  • (Python第六天)文件处理
  • (Redis使用系列) SpirngBoot中关于Redis的值的各种方式的存储与取出 三
  • (超简单)使用vuepress搭建自己的博客并部署到github pages上
  • (附源码)计算机毕业设计ssm本地美食推荐平台
  • (一)appium-desktop定位元素原理
  • (转)3D模板阴影原理
  • .net core控制台应用程序初识
  • .NET 的静态构造函数是否线程安全?答案是肯定的!
  • .NET 服务 ServiceController
  • .NET6 命令行启动及发布单个Exe文件
  • .NET框架
  • .net实现头像缩放截取功能 -----转载自accp教程网
  • /etc/sudoers (root权限管理)
  • /proc/interrupts 和 /proc/stat 查看中断的情况
  • :“Failed to access IIS metabase”解决方法
  • [20181219]script使用小技巧.txt
  • [Angular 基础] - 表单:响应式表单
  • [BZOJ] 2006: [NOI2010]超级钢琴
  • [C# WPF] 如何给控件添加边框(Border)?
  • [HNOI2008]水平可见直线