Container With Most Water

Category: Array

Deadline: 1st week (12/31 - 1/7)

Difficulty: Medium

Github: https://github.com/iamseokhyun/2022-algorithm-study/tree/master/array/ContainerWithMostWater/

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

Problem

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 <= 10^5
• 0 <= height[i] <= 10^4

Solution

public class Solution
{
    public int MaxArea(int[] height)
    {
        int l = 0;
        int r = height.Length - 1;
        int max = 0;
        int h;

        while (r > l)
        {
            h = (height[r] > height[l]) ? height[l] : height[r];
            max = (max > (h * (r - l))) ? max : (h * (r - l));

            if (height[r] > height[l])
            {
                l++;
            }
            else
            {
                r--;
            }
        }

        return max;
    }
}

Comment

• 3Sum 문제와 동일하게 좌측과 우측에서 접근하는 pointer를 이용하면 편하다. 솔직히 이해하는데 좀 오래 걸렸는데, Greedy Algorithm이라고 한다.
• 먼저 left = 0, right = h.Length - 1로 초기화해준다.
• 담을 수 있는 물의 면적(2차원이니까 면적이 맞지!)은 h[l], h[r] 중 최솟값 곱하기 r-l이다. 이를 계산해서 max에 먼저 넣는다.
• 우리는 r이나 l을 한칸씩 중심으로 옮기면서 최댓값을 찾을 것이다.
• h[r]과 h[l] 의 대소관계가 결정될텐데, h[r]이 h[l]보다 크다고 생각해보자. 즉 오른쪽 벽이 더 높은 상황이다. 그렇다면 왼쪽 벽을 고정하고 오른쪽 벽만을 좌측으로 움직일 때 현재의 max값보다 더 많이 담을 수 있을까? 애초에 왼쪽벽이 더 높이가 작았으므로 오른쪽 벽이 더 높아진다 하더라도 왼쪽 벽에 의해 높이가 계속 결정되며, r-l은 당연히 작아지므로 최댓값은 달라지지 않는다. (가로x세로에서 세로는 일정, 가로가 줄어듦)하물며 왼쪽 벽보다 오른쪽 벽이 낮아지면 결과는 당연히 작아진다. (가로 x 세로에서 둘다 줄어드니까). 그렇다면 왼쪽 벽을 고정한 상황에서 모든 경우에 대한 최댓값은 처음 상황이다. 즉 l을 한칸 우측으로 밀어서 동일한 4를 반복한다.
• 당연하지만 h[l]이 h[r]보다 크다면 4에서 좌/우만 바꾸어 생각하여 동일하게 우측벽을 고정하였을 때의 면적의 최댓값이 현재상태이며, 또다른 탐색을 위해서는 우측벽을 한칸 왼쪽으로 이동해야한다는 결론에 다다른다.
• 이렇게 하여 l > r이 되면 탐색이 끝난다. 계속 갱신하던 max값을 그대로 출력한 것이 답이다.