Algorithm/LeetCode
[LeetCode] 11. Container With Most Water (python)
유쾌한고등어
2023. 4. 6. 18:08
https://leetcode.com/problems/container-with-most-water/description/
Container With Most Water - LeetCode
Can you solve this real interview question? Container With Most Water - 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 toget
leetcode.com
해당문제는 bruteforce로 풀면 n^2의 시간복잡도가 걸려 시간초과가 난다.
투포인터로 풀면 n의 시간복잡도를 가진다.
이때 이해가 잘안갔던점은 왜 굳이 다음 스텝으로 넘어갈때 길이가 짧은 막대의 인덱스를 넘기는지였다.
즉, height[left] 와 height[right] 중 더 짧은 포인터 를 옮겨 그 다음을 순회하는 점이 이해가 잘 되지않았다.(left라면 left+1 , right 라면 right-1.)
container는 짧은 height 를 기준으로 물이 담아지기 때문에, 짧은 포인터를 옮겨야 그 다음 container의 크기가 커질 가능성이 있기때문이다.
SOLUTION CODE
# PYTHON
class Solution:
def maxArea(self, height: List[int]) -> int:
# # BRUTE FORCE
# res = 0
# for l in range(len(height)):
# for r in range(len(height)):
# area = (r - l) * min(height[l],height[r])
# res = max(res,area)
# return res
res = 0
l, r = 0, len(height) - 1
while l < r:
area = (r-l) * min(height[l],height[r])
res = max(res,area)
if height[l] < height[r]:
l += 1
else:
r -= 1
return res