[BOJ 6549] 히스토그램에서 가장 큰 직사각형 (Java)

#문제

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

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

#풀이

Stack을 이용하여 풀었다. 

순서대로 Stack에 막대바의 height, index 정보를 push하면서,

만약 현재 막대바의 height가 Stack의 top원소보다 작을 경우 Stack의 원소를 pop하면서 넓이를 계산해준다. 

 

#소스코드

package stack;

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


public class BOJ6549 {

    public static class Bar{
        int index;
        long height;
        public Bar(int index, long height){
            this.index = index;
            this.height = height;
        }
    }

    public static BufferedReader br;
    public static BufferedWriter bw;

    public static void pro(String s){
        long maxArea = 0;
        Stack<Bar> stack = new Stack<Bar>();

        StringTokenizer st = new StringTokenizer(s);
        int n = Integer.parseInt(st.nextToken());
        for(int i = 0; i <= n+1; i++){
            int h = (i == 0 || i == n+1) ? 0 : Integer.parseInt(st.nextToken());
            if(i == 0) {
                stack.push(new Bar(0, 0));
                continue;
            }
            while(stack.peek().height > h){
                Bar b = stack.pop();
                long height = b.height;
                int width = stack.isEmpty()? i : i - stack.peek().index-1;
                maxArea = Math.max(maxArea, height*width);
            }
            stack.push(new Bar(i, h));
        }
        System.out.println(maxArea);
    }

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        while(true){
            String s = br.readLine();
            if("0".equals(s)) System.exit(0);
            pro(s);
        }
    }
}