(Leetcode) 11 - Container With Most Water
기회가 되어 달레님의 스터디에 참여하여 시간이 될 때마다 한문제씩 풀어보고 있다.
https://leetcode.com/problems/container-with-most-water/
내가 작성한 풀이
일단 문제를 봤을 때 포인터를 2개를 써야겠다는 느낌이 왔다. 그래서 일단 포인터를 양 끝에 두고 끝에서 부터 조금씩 조여봐야겠다는 생각을 하였다. 조일 때 어떤 기준으로 줄여야 하나 고민을 해보았는데, 두 포인터중 현재 높이가 낮은 포인터를 조이는 방향으로 진행하면 되겠다 생각을 하였다.
class Solution {
public int maxArea(int[] height) {
int start = 0;
int end = height.length - 1;
int max = getArea(height, start, end);
while(start < end) {
if(height[start] >= height[end]) {
end--;
max = Math.max(max, getArea(height, start, end));
} else {
start++;
max = Math.max(max, getArea(height, start, end));
}
}
return max;
}
public int getArea(int[] height, int start, int end) {
if (start == end) {
return 0;
}
return getMinHeight(height[end], height[start]) * (end - start);
}
public int getMinHeight(int height1, int height2) {
return Math.min(height1, height2);
}
}
TC, SC
시간 복잡도는 O(n)이고, 공간 복잡도는 O(1)이다.