标签： C++ 算法 LeetCode 数组
每日算法——leetcode系列
问题 Trapping Rain Water
Difficulty: Hard
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
For example,
Given[0,1,0,2,1,0,1,3,2,1,2,1], return6.
<small>The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!</small>
class Solution {
public:
int trap(vector<int>& height) {
}
};
翻译
困住的雨水
难度系数：困难
给定n个代表地图中的高度的非负数的整数，每条的宽度为1，求下雨后能困住多少雨水。
例如：
给定[0,1,0,2,1,0,1,3,2,1,2,1], 返回 6.
思路
- 先找到最高的条柱
- 再两边往中间扫
- 扫左边时，如果当前柱左边的最大值是当前柱，就记录
- 不是当前柱，刚把水累加
代码
class Solution {
public:
int trap(vector<int>& height) {
int maxBarIndex = 0;
int index = 0;
for (auto item : height){
if (item > height.at(maxBarIndex)){
maxBarIndex = index;
}
index++;
}
int water = 0;
for (int i = 0, leftMax = 0; i < maxBarIndex; ++i){
if (height[i] > leftMax){
leftMax = height[i];
} else {
water += leftMax - height[i];
}
}
int n = static_cast<int>(height.size());
for (int i = n - 1, rightMax = 0; i > maxBarIndex; --i){
if (height[i] > rightMax) {
rightMax = height[i];
} else {
water += rightMax - height[i];
}
}
return water;
}
};
此题还有一种有栈的方式，以后再码。
