히스토그램

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

 

문제

---

히스토그램이란, 아래 그림과 같이 직사각형이 배열되어 있는 것을 말한다. 각 직사각형의 가로 길이는 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.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int[] b;
        int[] c;
        int d = 0;
        int max = Integer.MIN_VALUE;
        int result = 0;

        Stack<int[]> stack = new Stack<>();

        a = sc.nextInt();

        b = new int[a];

        for (int i = 0; i < a; i++) {
            b[i] = sc.nextInt();
        }
        sc.close();

        stack.push(new int[]{-1, -1});
        result = a;
        int tmp;
        for (int i = 0; i < a; i++) {

            while (!stack.isEmpty() && stack.peek()[0] >= b[i]) {
                stack.pop();
            }

            tmp = b[i] * (i - stack.peek()[1]);

            int j = i + 1;

            while (j < a && b[j] >= b[i]) {
                j++;
                tmp += b[i];
            }

            if (tmp > result) result = tmp;

            stack.push(new int[]{b[i], i});
        }

        System.out.println(result);

    }


}

제대로 푼 코드

///히스토그램

import java.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();

    //ex
    //7
    //2 1 4 5 1 4 4
    //answer
    //8
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int[] b;
        int[] c;
        int d = 0;
        int max = Integer.MIN_VALUE;
        int result = 0;

        Stack<int[]> stack = new Stack<>();

        a = sc.nextInt();

        b = new int[a + 1];
        b[a] = -1;

        for (int i = 0; i < a; i++) {
            b[i] = sc.nextInt();
        }
        stack.push(new int[]{-1, -1});

        sc.close();

        result = a;
        int tmp;
        for (int i = 0; i <= a; i++) {

            if (!stack.isEmpty() && stack.peek()[0] < b[i]) {
                stack.push(new int[]{b[i], i});
            } else {
                while (!stack.isEmpty() && stack.peek()[0] > b[i]) {
                    int[] tmpInt = stack.pop();
                    tmp = tmpInt[0] * (i - 1 - stack.peek()[1]);

                    if (tmp > result) result = tmp;
                }

                stack.push(new int[]{b[i], i});
            }
        }

        System.out.println(result);

    }


}