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]).
길이 n의 높이에 대한 정수배열이 주어집니다. 여기에는 n개의 수직선이 그려져 있으며, 선의 두 끝점은 (i, 0) 및 (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.
제일 물을 많이 함유하고 있는 두개의 라인을 포함 x축의 형태의 컨테이너를 찾으세요. 컨테이너가 최대한 담을 수 있는 양을 반환하세요. 컨테이너가 기울어져선 안됩니다.
일단 사진을 보면 명확하다. 높이도 높이지만 x축으로도 길어야하기 때문에 뭐 간단히 높이만 높아서는 안된다.
개꿀쓰하고, 무식하게 brute-force로 돌려봤다. 당연히 정답은 잘 나오지만 ... 시간 복잡도가 O(n²) 이였다. 그리고 뒤늦게 제약을 확인했다.
- n == height.length
- 2 <= n <= 10^5
- 0 <= height[i] <= 104
곰곰히 생각해보다가 두 포인터가 생각났다. 인강보다가 얼핏 들었던거 같은데 이런 경우에 문제에서 사용했던걸로 기억이 났다.
그리하여.. 정답쓰...
'Javascript > LeetCode' 카테고리의 다른 글
| 15. 3SUM (0) | 2023.06.13 |
|---|---|
| 2. Add Two Numbers (0) | 2023.05.27 |