LeetCode 42. 接雨水 (C++实现)

1. 题目形貌

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，盘算按此分列的柱子，下雨之后能接多少雨水。
示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
表明：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单元的雨水（蓝色部门表示雨水）。
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9
2. 解题思路

先盘算前缀数组pre，然后盘算后缀数组suf，最后遍历height，每一位上的能接雨水的量等于min(pre, suf) - height
3. 代码实现

1. class Solution {
2. public:
3.     int trap(vector<int>& height) {
4.         int ans = 0;
5.         int n = height.size();
6.         vector<int> pre(n);
7.         pre[0] = height[0];
8.         for(int i = 1; i < n; i++)
9.         {
10.             pre[i] = max(pre[i - 1], height[i]);
11.         }
12.         vector<int> suf(n);
13.         suf[n - 1] = height[n - 1];
14.         for(int i = n - 2; i >= 0; i--)
15.         {
16.             suf[i] = max(suf[i + 1], height[i]);
17.         }
19.         for (int i = 0; i < n; i++)
20.         {
21.             ans += min(pre[i], suf[i]) - height[i];
22.         }
23.         return ans;
24.     }
25. };

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。