forked from wuduhren/leetcode-python
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathcontainer-with-most-water.py
More file actions
executable file
·51 lines (42 loc) · 1.72 KB
/
container-with-most-water.py
File metadata and controls
executable file
·51 lines (42 loc) · 1.72 KB
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
"""
`l` and `r` are the points on width that form the area.
The height on `l` is `H[l]` and `r` is `H[r]`.
The area that form by `l` and `r` is `(r-l)*min(H[r], H[l])`.
We are going to calculate the area everytime we move `l` or `r`.
And maintain the `ans`, which is the max of all area.
Now, we put `l` and `r` at the beginning and at the end of the array.
We calculate the area and update `ans`, move `l` or `r` inward.
How are we going to find a larger area with shorter width that form by `l` and `r`?
The answer is, we move the `l` or `r` with shorter `H[l]` or `H[r]`, so we might get a larger `min(H[r], H[l])`, which leads to possibly larger area.
By doing this, we now have a new pair of `l` and `r`.
We calculate the area and update `ans`, move `l` or `r` inward.
...
We repeat the process until `l` and `r` collapse.
So by repeatedly moving `l` and `r` inward, we can run through all the shorter width that might form area larger than `ans`.
"""
class Solution(object):
def maxArea(self, H):
r, l = len(H)-1, 0
ans = float('-inf')
while r>l:
ans = max(ans, (r-l)*min(H[r], H[l]))
if H[r]>H[l]:
l = l+1
else:
r = r-1
return ans
class Solution(object):
def maxArea(self, height):
i = 0
j = len(height)-1
ans = 0
while i<j:
ans = max(ans, min(height[i], height[j])*(j-i))
if height[i]<height[j]:
"""
If we try to move the pointer at the longer line inwards, we won't gain any increase in area, since it is limited by the shorter line.
"""
i += 1
else:
j -= 1
return ans