Notice
Recent Posts
Recent Comments
Link
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
Tags
- 스프링익셉션처리
- 스프링부트사진올리기
- 스프링부트api
- 도커설치하는법
- 출처 문어박사
- 파이썬sort
- 출처 따배도
- WAS웹서버
- 출처 코딩셰프
- 스프링이미지업로드
- springboot_exception_handler
- 스프링부트중복예외처리
- dockerinstall
- 인스타클론
- ssh도커설치
- 스프링부트구독취소
- 서버에도커설치
- 우분투도커설치
- centos도커설치
- vm도커설치하는법
- 스프링부트
- 스프링부트팔로우취소
- 출처 노마드코더
- 스프링사진업로드
- 멀티폼
- 스프링구독
- 스프링부트팔로잉
- 스프링사진
- 출처 메타코딩
- 스프링부트서버에사진전송
Archives
- Today
- Total
MakerHyeon
[LeetCode] 11. Container With Most Water (python) 본문
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
'Algorithm > LeetCode' 카테고리의 다른 글
[LeetCode] 121. Best Time to Buy and Sell Stock (0) | 2023.04.19 |
---|---|
[LeetCode] 42. Trapping Rain Water (python) (0) | 2023.04.10 |
[LeetCode] 15. 3Sum (python,C++) (0) | 2023.03.14 |
[LeetCode] 1472. Design Browser History (python,C++) (0) | 2023.03.13 |
[LeetCode] 167. Two Sum II - Input Array Is Sorted (python,C++) (0) | 2023.03.13 |
Comments