본문 바로가기
알고리즘

[leetcode] 11. Container With Most Water

by Night-Owl 2022. 8. 13.
반응형

[leetcode] 11. Container With Most Water

문제


풀이
투 포인터로 풀면 된다.
배열의 처음(left)과 배열의 맨 끝부분(right)의 포인터를 이동하면서 가장 큰 area를 구하면 된다.
- area = (right - left) * min(height[left], height[right])

포인터의 이동은 left와 right의 height를 비교해서 left가 더 크면 right를 왼쪽으로 이동해주고 아니면 left를 오른쪽으로 이동해주면 된다. left가 right보다 크면 loop를 종료하면 된다.


코드

Java

class Solution {
    public int maxArea(int[] height) {
        int area = 0;
        int left = 0;
        int right = height.length - 1;

        while (left < right) {
            int tmpArea = (right - left) * Math.min(height[left], height[right]);
            area = Math.max(tmpArea, area);

            if (height[left] < height[right]) {
                left++;
            } else {
                right--;
            }
        }
        return area;
    }
}


Go

func maxArea(height []int) int {
	maxArea := 0
	left, right := 0, len(height)-1

	for left < right {
		tmpArea := (right - left) * min(height[left], height[right])

		if tmpArea > maxArea {
			maxArea = tmpArea
		}

		if height[left] < height[right] {
			left++
		} else {
			right--
		}

	}

	return maxArea
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}

참고

반응형

'알고리즘' 카테고리의 다른 글

[leetcode] 238. Product of Array Except Self  (0) 2022.07.18
[leetcode] 468. Validate IP Address  (0) 2022.03.15
[leetcode] 189. Rotate Array  (0) 2021.10.15
[leetcode] 784. Letter Case Permutation  (0) 2021.10.04
[leetcode] 733. Flood Fill  (0) 2021.10.03

댓글0