히스토그램==========

📍 문제 설명

💡 접근

현재 막대가 이전 길이의 막대보다 작을 때 넓이를 구해줘야 한다.

 

1.현재 막대 높이보다 크거나 같은 막대를 만나면 모두 pop 해준다.

2.pop할 때 높이와 폭을 계산해서 넓이를 구해준다.

3.현재 막대를 push 한다.

4.현재 막대가 이전 길이의 막대와 같거나 클 수 있으므로 남아있는 넓이들도 계산해줘야한다.

 

스택에는 인덱스를 기준으로 넣었지만 값들을 기준으로 한다.

i = 0일 때 push 한다. [2]
i = 1일 때 2를 pop 한다. []

넓이를 구한다. 높이 2 폭 1 -> 2 -> 비어있을 땐 i가 폭

현재 높이 push 한다. [1]

 

i = 2일 때 push 한다. [1,4]

i = 3일 때 push 한다. [1,4,5]

i = 4일 때 1,4,5를 pop 한다.

각각 pop시킬 때 넓이를 구한다.

코드 상에서는 스택에 막대의 번호를 넣어놨으니 폭은 i - 1 - s.peek()이 된다.

5일 때 높이 5 폭 (4-1-2) 1 -> 5 [1,4] 

4일 때 높이 4 폭 (4-1-1) 2 -> 8 [1]

1일 때 높이 1 폭 4 -> 4 [] -> 비어있을 땐 i가 폭

 

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, answer = Integer.MAX_VALUE;
    static int[][] board;
    static boolean[][] visited;
    static int[] histogram;
    static int[] dx = {-1, 0, 1, 0,}; //북동남서
    static int[] dy = {0, 1, 0, -1};

    public static void main(String[] args) {
        Main T = new Main();
        Scanner kb = new Scanner(System.in);

        n = kb.nextInt();
        histogram = new int[n];
        for(int i = 0; i < n; i++) {
            histogram[i] = kb.nextInt();
        }

        System.out.println(T.solution());
    }

    private long solution() {
        Stack<Integer> s = new Stack<>();
        //높이의 최댓값은 1,000,000,000
        long max = 0;

        //모든 막대 확인
        //i = 4일 때
        //h[3]에서의 넓이는 height 5 width 1(4-1-2) -> 5
        //h[2]에서의 넓이는 height 4 width 2(4-1-1) -> 8
        //h[1]에서의 넓이는 height 1 width 4(4)  -> 4
        for(int i = 0; i < n; i++) {
            //현재 막대의 높이 보다 크거나 같은 막대들은 모두 pop 해준다.
            while(!s.isEmpty() && histogram[s.peek()] >= histogram[i]) {
                //pop 시킬 때 직사각형의 넓이를 구해야한다.
                int height = histogram[s.pop()];
                //비어있을 땐 i가 폭이 되고 아니라면 현재 인덱스 - 1 - 막대번호가 폭이 된다.
                long width = s.isEmpty() ? i : i - 1 - s.peek();

                max = Math.max(max, height * width);
            }
            //현재 막대는 무조건 push 해준다.
            s.push(i);
        }

        //아직 처리 안된 넓이들에 대해서도 처리해야한다.
        //n = 7
        //height 3 width 2(7-1-4) -> 6
        //height 1 width 7(7) -> 7
        while(!s.isEmpty()) {
            int height = histogram[s.pop()];

            long width = s.isEmpty()? n : n - 1 - s.peek();

            max = Math.max(max, height * width);
        }

        return max;
    }

}