42.|42. 接雨水
题目
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
文章图片
image.png
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
思路
文章图片
image.png
自己在纸上画了一下思路,在上图,黑色虚线表示从左往右搜索的最大值,红色虚线表示从右往左搜索的最大值。有了这两个数组,对每一个柱子(立方体)取left和right最小值,这个最小值就是对应了
水面的顶(如果有的话),用这个顶减去
当前柱子的高度(水面的底),就是这个位置处对应的水量。由此得到结果。
【42.|42. 接雨水】
#include
#include
using namespace std;
class Solution {
public:
int trap(vector& height) {
int size = height.size();
vector left(size), right(size);
for (int i = 1;
i < size;
i++)
left[i] = max(left[i - 1], height[i - 1]);
for (int i = size - 2;
i >= 0;
i--)
right[i] = max(right[i + 1], height[i + 1]);
int water = 0;
for (int i = 0;
i < size;
i++)
{
int level = min(left[i], right[i]);
water += max(0, level - height[i]);
}
return water;
}
};
int main(int argc, char* argv[])
{
vector test = { 0,1,0,2,1,0,1,3,2,1,2,1 };
auto res = Solution().trap(test);
return 0;
}
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 基于微信小程序带后端ssm接口小区物业管理平台设计
- 2020-04-07vue中Axios的封装和API接口的管理
- 画解算法(1.|画解算法:1. 两数之和)
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- 宋仲基&宋慧乔(我们不公布恋情,我们直接结婚。)
- 考前焦虑——接纳情绪,转移注意力
- 调取接口时报404错误(ID:16)
- Hive常见问题汇总
- CICC(脑机接口,科幻几近成真())