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

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

6549번: 히스토그램에서 가장 큰 직사각형

---

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

public class Main {
    static int[] height;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();
        StringTokenizer st = new StringTokenizer(br.readLine());
        while (st.countTokens() != 1) {
            int n = Integer.parseInt(st.nextToken());
            height = new int[n];
            for (int i = 0; i < n; i++) {
                height[i] = Integer.parseInt(st.nextToken());
            }
            sb.append(getArea(n)).append("\n");
            st = new StringTokenizer(br.readLine());
        }
        System.out.println(sb);
    }

    private static long getArea(int n) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        for (int i = 0; i < n; i++) {
            int nowHeight = height[i];
            while (!stack.isEmpty() && height[stack.peek()] >= nowHeight) { //height[i]보다 높이가 높거나 같은 모든 막대 꺼내 최대 넓이 계산 (기준점이 i가 됨)
                int top = stack.pop();

                //마지막 막대인 경우 = 모든 막대가 nowHeight 보다 크거나 같음 => 최대 너비 width = i (= 0 ~ i-1)로 계산
                //마지막 막대 아닌 경우 = height[top]보다 작은 막대가 있다는 것 => 최대 너비 width = i-1 ~ 작은막대 (작은막대는 포함 X)
                long width = stack.isEmpty() ? i : i - 1 - stack.peek();
                maxArea = Math.max(maxArea, height[top] * width);
            }
            stack.push(i); //이후 i번째 막대 넣음
        }
        //모두 끝난 후 스택에 남아있는 막대 처리 (마지막 막대 높이보다 작은 막대들)
        while (!stack.isEmpty()) {
            int top = stack.pop();
            long width = stack.isEmpty() ? n : n - 1 - stack.peek();
            maxArea = Math.max(maxArea, width * height[top]);
        }
        return maxArea;
    }
}

💡 stack

풀이

• 막대의 인덱스, 높이 조합을 스택에 저장해 줌 (현재 인덱스 now, 스택 최상단 인덱스 top이라 하면)
  • h[top] <= h[now] => stack.push(npw)
  • h[top] > h[now] => h[now]보다 크거나 같은 값 모두 pop해서 각 막대 기준 최대 넓이 갱신
    • stack에서 peek한 막대 별 최대 높이를 구해 갱신한다 => (now - stack.peek()-1) * h[stack.peek()])  (=> 남은 스택 중 현재 가장 큰 높이는 stack.peek()의 높이이므로)
    • 이때 하나 뽑고 스택이 비었으면(= 남은 스택에 현재 막대보다 작은 막대가 없음) => 그냥 너비를 (now)로 함
    • 최대값 갱신한 후, 스택에 현재 막대를 넣고 다음 막대로 넘어감
    • => 현재 막대보다 짧은 막대들의 최대 넓이는 추후에 구해 질 예정
  • 마지막 막대까지 끝난 경우, 스택에 막대가 아직 남아있다면 남아있는 막대들로 동일하게 실행