백준 6549 자바 - 히스토그램에서 가장 큰 직사각형 문제

www.acmicpc.net/problem/6549

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

 

스택을 통한 풀이로

스택에서 꺼낸 인덱스의 직사각형의 높이가 더 큰 경우 스텍에서 해당 인덱스를 꺼내서 계산

스택에서 꺼내지지 않고 순회가 끝나고도 스택에 있는 경우에 꺼내서 계산

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

// 히스토그램에서 가장 큰 직사각형 문제 - 6549번
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        while(true) {
            st = new StringTokenizer(br.readLine());

            int n = Integer.parseInt(st.nextToken());
            if(n==0) break;

            int[] height = new int[n];
            Stack<Integer> stack = new Stack<>();
            long max = 0;
            for(int i = 0; i < n; i++) {
                height[i] = Integer.parseInt(st.nextToken());
            }

            for(int i=0;i<n;i++) {
                while(!stack.isEmpty() && height[stack.peek()] > height[i]) {
                    int idx = stack.pop();
                    int width = stack.isEmpty()? i: i-stack.peek()-1;
                    max = Math.max(max, (long)width*height[idx]);
                }
                stack.push(i);
            }

            while(!stack.isEmpty()) {
                int idx = stack.pop();
                int width = stack.isEmpty()? n: n-stack.peek()-1;
                max = Math.max(max, (long)width*height[idx]);
            }

            System.out.println(max);
        }
    }
}