[LeetCode][Greedy] 11. Container With Most Water

 

 

 

문제 링크

https://leetcode.com/problems/container-with-most-water/

Container With Most Water - LeetCode

Given n non-negative integers a1, a2, ..., an , where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of the line i is at (i, ai) and (i, 0). Find two lines, which, together with the x-axis forms a container, such that the container contains the most water.

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

Example 3:

Input: height = [4,3,2,1,4]
Output: 16

Example 4:

Input: height = [1,2,1]
Output: 2

 

Constraints:

• n == height.length
• 2 <= n <= 105
• 0 <= height[i] <= 104

 

 

문제 해석

 

처음엔 아무생각없이 2중 for문 돌려서 제출해 봤는데 문제를 너무 쉽게 보았.. (당연히 Time Limited.. ㅎㅎㅎ)

n^2보다 줄여야겠다 하고 고민하던 중.. 

 

우선, width가 넓을 수록 좋다! 생각이 되어서 가장 끝을 from, to로 두고 줄여야겠다 싶었다.

그리고, 그 중 작은걸 해소해야 값이 더 커지겠구나 싶어서 둘 중 작은거를 처리해 주기로 하였다.

 

이를 기반으로 from, to를 조정하여 점점 접혀보았고 아래 두 경우의 탈출 조건을 체크하였다.

• from과 to가 엇갈릴 경우
• 더이상 움직일만 하지 않을 경우

 

 

 

제출 코드

 

public int maxArea(int[] height) {
  int max = 0;
  int from = 0;
  int to = height.length - 1;

  while(from < to) {
    int _from = from;
    int _to = to;

    int area = ((_to - _from) * (height[_from] < height[_to] ? height[_from] : height[_to]));
    if (max < area) max = area;

    if (height[_from] < height[_to]) {
    	while (height[_from] >= height[from] && (from < to)) from++;
    }
    else {
    	while(height[to] <= height[_to] && (from < to)) to--;
    }

    if (from == _from && to == _to) break;
  }

  return max;
}

 

 

 

 

제출 결과

 

 

참고 링크

 

 

 

 

 

개인적으로 while문을 쓰는걸 좋아하지 않지만.. 어쩔 수 없다능 ㅠ.ㅠ

- mushroong

 

 

 

 

---