[Leetcode] 11. Container With Most Water 문제 풀이

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

Container With Most Water - LeetCode

문제 내용

댐 높이가 주어졌을 때 2개의 댐 사이에 있는 물의 양이 가장 큰 값을 구하는 문제

 

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

문제 풀이

댐의 높이는 2개의 댐중에 작은 것으로 정해진다.

모든 댐을 다 살펴 볼 필요 없다.

물의 양을 정하는 것은 댐이 작은 것이기 때문에

2개의 댐 중에 작은 부분 (높이를 결정하는 댐)을 1개 이동하면서 구하면 된다.

높이는 작은 댐으로 결정되기 때문에 높이가 큰 댐을 이동하면 높이가 변하지 않고 거리가 줄어들기 때문에 소용없다.

 

코드

class Solution {
public:
    int maxArea(vector<int>& height) {
        int s = 0;
        int e = height.size()-1;
        
        int maxArea = 0;
        while (s < e) {
            if (height[s] < height[e]) {
                maxArea = max(maxArea, height[s] * (e-s));
                s++;
            } else {
                maxArea = max(maxArea, height[e] * (e-s));
                e--;
            }
        }
        
        return maxArea;
    }
};