LeetCode 42. 接雨水 (C++实现)
1. 题目形貌给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，盘算按此分列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height =
输出：6
表明：上面是由数组 表示的高度图，在这种情况下，可以接 6 个单元的雨水（蓝色部门表示雨水）。
示例 2：
输入：height =
输出：9
2. 解题思路
先盘算前缀数组pre，然后盘算后缀数组suf，最后遍历height，每一位上的能接雨水的量等于min(pre, suf) - height
3. 代码实现
class Solution {
public:
int trap(vector<int>& height) {
int ans = 0;
int n = height.size();
vector<int> pre(n);
pre = height;
for(int i = 1; i < n; i++)
{
pre = max(pre, height);
}
vector<int> suf(n);
suf = height;
for(int i = n - 2; i >= 0; i--)
{
suf = max(suf, height);
}
for (int i = 0; i < n; i++)
{
ans += min(pre, suf) - height;
}
return ans;
}
};
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]