-
Notifications
You must be signed in to change notification settings - Fork 0
/
container_with_most_water_tp.cpp
59 lines (52 loc) · 1.26 KB
/
container_with_most_water_tp.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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
/**
* Two pointer solution
* Time: O(n)
* Space: O(1)
* Author: Teddy
* Date: 04-02-2015
*/
/**
* TWO CASES COMPARE TO DISCARD WHICH EDGE
* * * * * * * * * * * * * * *
* Array: 3 1 2 3 4 5 6 3 4 2
* Size: 10
* area[0 - 9] = 20;
* area[0 - 8] = 27;
* area[1 - 9] = 9;
* * * * * * * * * * * * * * *
* Array: 3 4 1 2 3 4 5 6 1 2
* Size: 10
* area[0 - 9] = 20;
* area[0 - 8] = 9;
* area[1 - 9] = 18;
*/
/**
* The above two cases prove that, we should discard the little edge of current
* pool, because we want to keep the lower edge of the pool be larger when the
* length of the get smaller.
*/
class Solution {
private:
int area(int i, int j, int valuei, int valuej){
int min = valuei >= valuej ? valuej : valuei;
return (j - i) * min;
}
public:
int maxArea(vector<int> &height) {
int front = 0;
int end = height.size() - 1;
int maxArea = 0;
int curArea;
while(front < end){
curArea = area(front, end, height[front], height[end]);
maxArea = maxArea >= curArea ? maxArea, curArea;
if(height[front] >= height[end]){
++end;
}
else{
++front;
}
}
return maxArea;
}
};