題目
給定 n 個(gè)非負(fù)整數(shù)表示每個(gè)寬度為 1 的柱子的高度圖讲逛，計(jì)算按此排列的柱子鸵闪，下雨之后能接多少雨水怀愧。
image.png
示例:
輸入: [0,1,0,2,1,0,1,3,2,1,2,1]
輸出: 6
思路
image.png
自己在紙上畫(huà)了一下思路怔昨，在上圖独旷，黑色虛線表示從左往右搜索的最大值署穗，紅色虛線表示從右往左搜索的最大值。有了這兩個(gè)數(shù)組嵌洼，對(duì)每一個(gè)柱子（立方體）取left和right最小值案疲，這個(gè)最小值就是對(duì)應(yīng)了水面的頂（如果有的話），用這個(gè)頂減去當(dāng)前柱子的高度（水面的底）麻养，就是這個(gè)位置處對(duì)應(yīng)的水量褐啡。由此得到結(jié)果。
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int trap(vector<int>& height) {
int size = height.size();
vector<int> 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<int> test = { 0,1,0,2,1,0,1,3,2,1,2,1 };
auto res = Solution().trap(test);
return 0;
}
