You are given an integer array height of length n. There are n vertical lines drawn such that the two endpoints of the ith line are (i, 0) and (i, height[i]).
Find two lines that together with the x-axis form a container, such that the container contains the most water.
Return the maximum amount of water a container can store.
Notice that you may not slant the container.
Example 1:
Input: height = [1,8,6,2,5,4,8,3,7]
Output: 49
Explanation: The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
Example 2:
Input: height = [1,1]
Output: 1
Constraints:
n == height.length
2 <= n <= 105
0 <= height[i] <= 104
완전 탐색의 경우 10000^2 이므로 억단위의 시간 복잡도가 나온다.
때문에 시간 복잡도를 고려하면 복잡도가 n인 알고리즘을 구현 해야한다.
문제를 잘 살펴보면 중간에 큰 막대기에 관계 없이 전체의 물의 저장량이 고정된다.
때문에 우리는 좌우로 범위를 좁혀나가면서 진행하는 sliding window 즉 2 pointer로 문제를 접근한다.
높이가 동일한 경우에 문제가 발생할 여지가 있다.
그러나 동일할 때는 아무쪽이나 줄여줘도 상관없다.
구체적으로 3 1 100 100 2 3 에서 뒷쪽에서부터 줄이는 것이 유리하다.
그러나 우리는 최댓값을 구한다. 작은 녀석들은 최댓값을 갱신시키지 못한다.
결국엔 큰 녀석들만 중요하다는 이야기이다.
10 1000 500 10 의 경우 어느쪽으로 진행하더라고 500이라는 물의 크기에 도달이 가능하다.
class Solution:
def maxArea(self, height: List[int]) -> int:
start = 0
end = len(height) - 1
water = 0
# sliding window
while start < end:
temp_water = min(height[start], height[end]) * abs(start - end)
water = max(temp_water, water)
# when start side is smaller than end side!
if height[start] < height[end]:
start += 1
else:
end -= 1
return water