[백준]6549_히스토그램에서 가장 큰 직사각형

https://www.acmicpc.net/problem/6549

문제 설명
그림처럼 연속되는 사각형들 중에서 합쳐서든 혼자든 넓이가 가장 큰 사각형의 넓이를 구하면 되는 문제

풀이
문제를 이해하는데 어려움은 없었지만, 입력이 10의5승으로 크기 때문에 O(N^2) 미만의 시간복잡도 풀이를 찾아야했다. 
처음 아이디어는 배열에 높이 정보를 입력받고, 높이, 너비, 이전 높이 정보를 활용해서 뒤에서부터 높이를 구하려했다.
1. 현재 높이가 전 높이보다 낮아진거면 길이 증가, 높이는 현재값으로 하여 넓이구하고, 최대값 갱신
2. 현재 높이가 더 크다면 길이 1, 높이 현재값으로하여 넓이 구하고 최대값 갱신
이 풀이 틀렸음.
높이가 [1 2 3 4 5] 인경우 값이 잘 나오지만 반대인경우는 값이 틀려지기 때문

맞는 풀이 (STACK사용)
스택 자료구조를 활용하여 다음과같은 규칙으로 풀이
1. 스택이 비어있으면 현재 높이를 스택에 PUSH
2. 그렇지 않으면, 현재값과 스택의 값을 비교,
2-1. 현재 값이 더 큰 경우 : 값을 추가한다.
2-2. 작은 경우 : POP()한 값을 높이로 사용, 그다음 PEEK()한 값을 이용하여 길이를 구한다. 
(길이 구하는 공식: 현재 인덱스 - 스택에 있는 값(인덱스) - 1) 
3. 2번에 포함되는 과정을 스택의 값이 비거나, 현재값이 스택의 값보다 클 때까지 반복.
4. 마지막으로 스택에 남아있는 값을 꺼내어 넓이 비교, 최신값 갱신.

코드

package BJ;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Stack;
import java.util.StringTokenizer;

public class BJ_6549_히스토그램에서가장큰직사각형 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());  // 직사각형의 수
            if (n == 0) break;  // 입력의 마지막 줄에 0이 주어짐

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

            System.out.println(getMaxRectangleArea(heights, n));
        }
    }

    public static long getMaxRectangleArea(int[] heights, int n) {
        Stack<Integer> stack = new Stack<>();  // 인덱스를 저장하는 스택
        long maxArea = 0;  // 최대 넓이를 저장할 변수

        for (int i = 0; i < n; i++) {
            // 스택이 비어 있지 않고, 현재 높이가 스택의 top이 가리키는 높이보다 작으면
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];  // 스택에서 pop하여 높이 획득
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;  // 너비 계산
                maxArea = Math.max(maxArea, (long) height * width);  // 최대 넓이 갱신
            }
            stack.push(i);  // 현재 인덱스를 스택에 push
        }

        // 남은 스택을 처리하여 최대 넓이 확인
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? n : n - stack.peek() - 1;
            maxArea = Math.max(maxArea, (long) height * width);
        }

        return maxArea;
    }
}