- Notifications
You must be signed in to change notification settings - Fork 35
Expand file tree
/
Copy pathtrapping-rain-water.cpp
More file actions
Latest commit
21 lines (20 loc) · 569 Bytes
/
Copy pathtrapping-rain-water.cpp
File metadata and controls
21 lines (20 loc) · 569 Bytes
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/*
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
--||author : Mitternachtsmond||--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
*/
classSolution
{
public:
inttrap(vector<int>& height) {
int n=height.size();
vector<int>premax(n),suffmax(n);
premax[0]=height[0];
for(int i=1;i<n;i++) premax[i]=max(premax[i-1],height[i]);
suffmax[n-1]=height[n-1];
for(int i=n-2;i>=0;i--) suffmax[i]=max(suffmax[i+1],height[i]);
int ans=0;
for(int i=1;i<n-1;i++) ans=ans+(min(premax[i],suffmax[i])-height[i]);
return ans;
}
};