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
33 lines (27 loc) · 1.22 KB
/
container-with-most-water.py
File metadata and controls
33 lines (27 loc) · 1.22 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
"""
`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