-
Notifications
You must be signed in to change notification settings - Fork 1
/
0011.cpp
40 lines (34 loc) · 967 Bytes
/
0011.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
int maxArea(vector<int>& height) {
map<int, int> last;
for (int i = 0; i < height.size(); i++)
last[height[i]] = i;
auto maxx = 0;
vector<int> prune;
for (int i = 0; i < height.size(); i++)
{
int left = height.size() - i;
int minHeight = maxx / left;
prune.clear();
auto l = last.lower_bound(minHeight);
for (; l != last.end(); l++)
{
auto h = l->first;
auto w = l->second - i;
if (w <= 0)
{
prune.push_back(h);
continue;
}
auto area = min(h, height[i]) * w;
if (maxx < area)
maxx = area;
}
// prune
for (auto h : prune)
last.erase(h);
}
return maxx;
}
};