8-8: 히스토그램에서 가장 큰 직사각형 찾기

히스토그램에서 가장 큰 직사각형 찾기

 

문제

---

히스토그램이란, 아래 그림과 같이 직사각형이 배열되어 있는 것을 말한다. 각 직사각형의 가로 길이는 1로 모두 같고, 세로 길이는 다를 수 있다. 예를 들어, 아래 그림은 높이가 2, 1, 4, 5, 1, 3, 3 인 직사각형으로 이루어진 히스토그램이다.

히스토그램이 주어질 때, 가장 큰 직사각형의 너비를 출력하는 프로그램을 작성하시오. 위의 예제에서는 최대 직사각형의 너비가 그림과 같이 8이다.

 

입력

---

첫째 줄에 히스토그램을 이루는 직사각형의 개수 N이 주어진다. ( 1 ≤ N ≤ 100,000 ) 둘째 줄에는 각 직사각형의 높이가 주어진다.  

출력

---

최대 직사각형의 너비를 출력한다.

 

예제 입력

7
2 1 4 5 1 3 3

예제 출력

8

 

출처

University of Ulm local contest 2003 H  

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

public class histogram {
    /**
     *
     *
     *
     *
     *
     *
     * @param args
     */
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
        int histogram[] = new int[N];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i=0; i<N; i++){
            histogram[i] = Integer.parseInt(st.nextToken());
        }

        ArrayDeque<Integer> stack = new ArrayDeque<>();

        int maxArea = 0;
        for (int i=0; i<N; i++){
            if (stack.isEmpty() || histogram[i] > histogram[stack.peek()]){
                stack.push(i);
            } else {
                while (!stack.isEmpty() && histogram[i] <= histogram[stack.peek()]){
                    //use top of stack as height
                    int height = histogram[stack.peek()];
                    stack.pop();
                    int width = stack.isEmpty()? i: i - stack.peek()-1;
                    if (height*width > maxArea){
                        maxArea =  height*width;
                    }
                }
                if (stack.isEmpty() || histogram[i] > histogram[stack.peek()]){
                    stack.push(i);
                }
            }
        }

        while (!stack.isEmpty()){
            //use top of stack as height
            int height = histogram[stack.peek()];
            stack.pop();
            int width = stack.isEmpty()? N: N - stack.peek()-1;
            if (height*width > maxArea){
                maxArea =  height*width;
            }
        }

        System.out.println(maxArea);

    }
}