ABOUT ME

-

Today
-
Yesterday
-
Total
-
  • 8-8: 히스토그램에서 가장 큰 직사각형 찾기
    Stacks, Queues 2018. 10. 25. 21:31

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

     

    문제


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

    alt text

    히스토그램이 주어질 때, 가장 큰 직사각형의 너비를 출력하는 프로그램을 작성하시오. 위의 예제에서는 최대 직사각형의 너비가 그림과 같이 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);

    }
    }


    'Stacks, Queues' 카테고리의 다른 글

    8-9: 탑  (0) 2018.10.25
    8-7: 괄호의 값  (0) 2018.10.25
    8-5: 괄호 Valid Parentheses String  (0) 2018.10.25
    8-4: 원형 큐 구현하기  (0) 2018.10.25
    8-3: 큐 구현하기  (0) 2018.10.25
Designed by Tistory.