Largest Rectangle in Histogram

https://leetcode.com/problems/largest-rectangle-in-histogram/

배열로 높이가 주어지고 각 인덱스의 넓이가 1일 때 만들어지는 사각형 중 가장 큰 크기를 갖고 있는 사각형의 크기를 찾는 문제이다. 사각형을 이루는 모양은 기본적으로 양 쪽의 높이가 현재 이루고 있는 사각형보다 작을 때 해당 시점의 높이에서 최대의 넓이를 가진 사각형이 된다.

이와 같은 성질을 위해서 스택을 이용했다. 값이 순서대로 늘어나는 경우를 저장하고, 값이 감소하는 위치를 확인할 경우 해당 인덱스를 기준으로 이전 인덱스들에서 가능한 사각형의 넓이를 구할 수 있다. 스택에서 값을 하나 씩 빼며 가능한 넓이를 계산하여 최대 값을 확인하고, 해당 높이의 값들을 구했기 때문에 해당 위치의 높이를 낮은 상태라고 가정이 가능하다.

 

 

4 - 2 - 1 - 3 와 같은 높이 값이 있다면 아래와 같은 형태로 계산을 해간다.
4
4 - 2
2 - 2
2 - 2 - 1
1 - 1 - 1 - 3
1 - 1 - 1 - 1

1. 4를 스택에 저장한다.
2. 2를 저장해야 하지만 이전 값이 더 크기 때문에 2 보다 큰 스택 안의 값들을 꺼내며 넓이를 구한다.
3. 빼낸 값은 현재의 값으로 다시 저장한다.
4. 1을 저장한다.
5. 크기가 줄어 들었으므로 이전 높이가 2인 경우의 사각형 넓이를 계산한다.
6. 2 높이는 의미가 없어지고 현재 값인 1인 값으로 계산한다.
7. 3 을 저장한다.
8. 배열 전체 순회가 끝난 이후 스택에서 값을 빼며 계산해간다. 3을 계산한 이후 그 이전값으로 변경한 이후 1 높이의 넓이를 구한다.

 

 

위와 같은 규칙으로 스택을 이용하여 통과한 최종 코드는 아래와 같다.

import java.util.*;  
  
public class Solution {  
    public int largestRectangleArea(int[] heights) {  
        int answer = 0;  
        Deque<Integer> stack = new ArrayDeque<>();  
        stack.addLast(heights[0]);  
  
        int width;  
        for(int i = 1; i < heights.length; i++){  
            int h1 = heights[i];  
            width = 1;  
            while(!stack.isEmpty() && stack.peekLast() > h1){  
                int h2 = stack.pollLast();  
                answer = Math.max(h2 * width, answer);  
                width++;  
            }  
  
            while(width-- > 0){  
                stack.addLast(h1);  
            }  
        }  
  
        width = 1;  
        while(!stack.isEmpty()){  
            int h2 = stack.pollLast();  
            answer = Math.max(h2 * width, answer);  
            width++;  
        }  
  
        return answer;  
    }  
}