[Grind75-LeetCode] Largest Rectangle in Histogram - Hard
접근
- 스택
풀이
Grind75의 마지막 문제로 히스토그램에서 가장 큰 사각형의 넓이를 구하는 문제이다. 이렇게 넓이를 구하는 유사한 문제에선 거의 슬라이딩 윈도우나 투 포인터를 사용했었지만 이번 문제는 끝 포인터들의 길이만 체크하는 것이 아니기 때문에 사용하기 어려운 방법이다.
어떻게 보면 더 간단한 방법일 수 있는데 스택을 사용해 푸는 것이다. 스택에 배열을 순회하며 값을 넣는다. 이전 스택에 들어있는 peek 값과 다음 진행에서 현재 인덱스의 값을 비교해 peek 값 보다 현재 인덱스 값이 크다면 스택에 값을 추가한 뒤 넘어가고 현재 인덱스 값이 작다면 스택에서 값을 꺼내 계산해 주면 된다. 쉽게 말해 스택에 추가되는 인덱스 들은 이전에 추가된 스택 peek의 값을 높이로 사용해 사각형을 이어 만들 수 있는 상태라는 뜻이고 스택에서 꺼내 계산해야 하는 경우는 스택의 peek의 값을 높이로 사용할 때 사각형 유지가 어렵기 때문에 계산을 해주게 되는 것이다.
heights = [2,1,5,6,2,3]
i = 0, heights[i] = 2
stack = [0(2)]
i = 1, heights[i] = 1
heights[stack.peek] < heights[1] = 2 < 1 -> 높이가 2인 사각형을 이어 만들 수 없음
//stack.peek의 인덱스 부터 현재 인덱스 전인 i = 0 까지의 넓이 계산
heights[stack.pop] * 1 = 2
max = 2
//현재 인덱스 push
stack = [1(1)]
i = 2, heights[i] = 5
heights[stack.peek] < heights[2] = 1 < 5 -> 높이가 1인 사각형을 이어 만들 수 있음
stack = [1(1), 2(5)]
i = 3, heights[i] = 6
heights[stack.peek] < heights[3] = 5 < 6 -> 높이가 5인 사각형을 이어 만들 수 있음
stack = [1(1), 2(5), 3(6)]
i = 4, heights[i] = 2
heights[stack.peek] < heights[4] = 6 < 2 -> 높이가 6인 사각형을 이어 만들 수 없음
//stack.peek의 인덱스 = 3 현재 인덱스 = 4로 높이 6 * 길이 1 계산
heights[stack.pop] * 1 = 6
max = 6
heights[stack.peek] < heights[4] = 5 < 2 -> 높이가 5인 사각형을 이어 만들 수 없음
//stack.peek의 인덱스 = 2 현재 인덱스 = 4로 높이 5 * 길이 2 계산 (인덱스 2, 3번을 2번의 높이를 기준으로 사각형으로 만드는 경우)
heights[stack.pop] * 2 = 10
max = 10
heights[stack.peek] < heights[4] = 1 < 2 -> 높이가 1인 사각형을 이어 만들 수 있음
//stack.peek의 인덱스 부터 현재 인덱스 4 까지의 모든 사각형이 높이가 1 이상이므로 사각형을 만들 수 있음
stack = [1(1), 4(2)]위와 같이 스택에 새로 추가되는 값들은 무조건 이전 스택에 들어있는 모든 값 보다 커야 하기 때문에 모든 경우의 사각형을 한 번의 배열 순회로 해결할 수 있다.
public int largestRectangleArea(int[] heights) {
Stack<Integer> stk = new Stack<>();
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
int currentHeight = heights[i];
while (!stk.isEmpty() && currentHeight < heights[stk.peek()]) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? i : i - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stk.push(i);
}
while (!stk.isEmpty()) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? heights.length : heights.length - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}위에 적었던 흐름 그대로이다. 현재 값과 스택의 peek 값을 비교해 현재 값이 더 크다면 스택에 추가한 뒤 넘어가고 현재 값이 더 작다면 이어서 사각형을 만들 수 없는 경우들을 계산한 뒤 스택에 추가하고 넘어간다. 그리고 마지막 인덱스 처리가 끝난 뒤 스택에 값이 남아있을 수 있기 때문에 마지막 계산을 해준 뒤 최대 값을 반환한다.
Deque
이전에 어떤 포스팅에서도 설명했던 부분인데 스택을 사용하는 경우 스택 대신 Deque를 사용해 주는 것만 해도 성능을 향상할 수 있다. 이전 포스팅에선 스택은 Vector 기반의 동적 배열을 사용하고 Deque는 Collection 기반이기 때문에 리사이징에서 성능 차이가 발생한다라고 했었는데 그 부분은 틀린 얘기였던 것 같다. 다시 찾아본 결과 스택은 Vector 클래스를 확장하여 구현되는데 Vector 클래스의 경우 모든 메서드는 synchronized 키워드가 사용된다. 즉 Stack은 멀티 스레드 환경에서 사용할 수 있게 각 연산마다 락을 획득하고 해제하는 과정이 필요하여 오버헤드가 발생하게 되는 것이다. 이 과정은 멀티 스레드 환경에선 안전성을 보장하지만 지금 코딩테스트와 같은 단일 스레드 환경에선 불필요한 오버헤드가 되는 것이다. Deque의 경우 동기화 메커니즘을 사용하지 않기 때문에 스택의 동기화 과정에서 발생하는 오버헤드가 없어 훨씬 빠르게 동작하는 것처럼 보였던 것이다.
public int largestRectangleArea(int[] heights) {
Deque<Integer> stk = new ArrayDeque<>();
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
int currentHeight = heights[i];
while (!stk.isEmpty() && currentHeight < heights[stk.peek()]) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? i : i - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stk.push(i);
}
while (!stk.isEmpty()) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? heights.length : heights.length - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}코드 자체는 Deque와 구현체로 ArrayDeque를 사용하게만 변경하면 정상적으로 동작한다.
스택 사용 X
스택도 사용하지 않고 성능을 높이는 코드들이 있었다. 알고리즘 자체는 동일하나 스택 대신 배열을 통해 스택처럼 구현한 코드였다.
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int result = 0;
int index = 0;
int[] arrayStack = new int[n+1];
int[] modifiedHeights = new int[n+2];
arrayStack[0] = 0;
modifiedHeights[0] = -1;
modifiedHeights[n + 1] = -1;
for(int i = 1; i <=n; i++)
{
modifiedHeights[i] = heights[i-1];
}
for(int i = 1; i <= n + 1; i++)
{
int currentHeight = modifiedHeights[i];
while(modifiedHeights[arrayStack[index]] > currentHeight)
{
int currTop = arrayStack[index--];
result = Math.max(result, (i - arrayStack[index] - 1) * modifiedHeights[currTop]);
}
arrayStack[++index] = i;
}
return result;
}배열을 사용해 입출력 오버헤드를 없앤 코드였다.
전체 코드
스택
class Solution {
public int largestRectangleArea(int[] heights) {
Stack<Integer> stk = new Stack<>();
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
int currentHeight = heights[i];
while (!stk.isEmpty() && currentHeight < heights[stk.peek()]) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? i : i - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stk.push(i);
}
while (!stk.isEmpty()) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? heights.length : heights.length - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}
}
Deque
class Solution {
public int largestRectangleArea(int[] heights) {
Deque<Integer> stk = new ArrayDeque<>();
int maxArea = 0;
for (int i = 0; i < heights.length; i++) {
int currentHeight = heights[i];
while (!stk.isEmpty() && currentHeight < heights[stk.peek()]) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? i : i - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
stk.push(i);
}
while (!stk.isEmpty()) {
int height = heights[stk.pop()];
int width = (stk.isEmpty()) ? heights.length : heights.length - stk.peek() - 1;
maxArea = Math.max(maxArea, height * width);
}
return maxArea;
}
}
스택 X
class Solution {
public int largestRectangleArea(int[] heights) {
int n = heights.length;
int result = 0;
int index = 0;
int[] arrayStack = new int[n+1];
int[] modifiedHeights = new int[n+2];
arrayStack[0] = 0;
modifiedHeights[0] = -1;
modifiedHeights[n + 1] = -1;
for(int i = 1; i <=n; i++)
{
modifiedHeights[i] = heights[i-1];
}
for(int i = 1; i <= n + 1; i++)
{
int currentHeight = modifiedHeights[i];
while(modifiedHeights[arrayStack[index]] > currentHeight)
{
int currTop = arrayStack[index--];
result = Math.max(result, (i - arrayStack[index] - 1) * modifiedHeights[currTop]);
}
arrayStack[++index] = i;
}
return result;
}
}'알고리즘 > 코딩테스트-Grind75' 카테고리의 다른 글
| [Grind75-LeetCode] Merge k Sorted Lists JAVA (0) | 2024.12.06 |
|---|---|
| [Grind75-LeetCode] Maximum Profit in Job Scheduling JAVA (0) | 2024.12.05 |
| [Grind75-LeetCode] Basic Calculator JAVA (0) | 2024.12.04 |
| [Grind75-LeetCode] Word Ladder JAVA (0) | 2024.12.03 |
| [Grind75-LeetCode] Find Median from Data Stream JAVA (0) | 2024.11.30 |