[백준 / 플레5] 6549 히스토그램에서 가장 큰 직사각형 (Java)

문제 보기

사용한 것

• 히스토그램에서 가장 큰 직사각형을 효율적으로 구하기 위한 Stack

풀이 방법

• heights의 마지막 인덱스에 -1을 넣고 stack에 -1을 push()한다.
  • 사용할 전략이 현재 인덱스 높이가 더 작은 경우 stack에 쌓은 값들로 직사각형의 넓이를 구하므로 heights의 마지막 인덱스에 -1을 넣는 것이다.
  • stack에 -1을 push()하는 이유는 기본적인 left를 정의해준 것이다.
• 현재 인덱스(right)를 증가시키며
  • 현재 인덱스가 stack의 top보다 같거나 큰 값이 들어오면 push()만 수행한다.
  • 현재 인덱스가 stack의 top보다 작은 경우 현재 인덱스의 높이보다 stack 원소의 높이가 더 클때까지 직사각형 넓이를 계산한다.
    • stack에는 오름차순으로 정렬되어있기 때문에 pop()한 mid의 높이가 left의 것보다 크고 right - 1의 높이보다 작다.
    • 따라서 mid의 높이를 가지는 직사각형은 heights[mid] * (right - left - 1)이다.

코드

public class Main {

    public static void main(String[] args) throws IOException {
        // 초기화
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int n, mid, left;
        int[] heights;
        long answer;
        Stack<Integer> stack;
        while (true) {
            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());

            if (n == 0) {
                break;
            }

            heights = new int[n + 1];
            for (int i = 0; i < n; i++) {
                heights[i] = Integer.parseInt(st.nextToken());
            }

            // Stack
            answer = 0;
            heights[n] = -1;
            stack = new Stack<>();
            stack.push(-1);
            for (int right = 0; right < heights.length; right++) {
                while (stack.size() > 1 && heights[right] < heights[stack.peek()]) {
                    mid = stack.pop();
                    left = stack.peek();
                    answer = Math.max((long) heights[mid] * (right - left - 1), answer);
                }
                stack.push(right);
            }
            sb.append(answer).append(lineSeparator());
        }

        System.out.println(sb);
    }
}