[백준] 11861 Maximal Area

문제

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

부가설명

코드 및 부가 설명은 제가 따로 주석처리로 설명을 해놓았습니다.
코드 참고하시면서 보시면 조금 더 편리하게 이해하실 수 있으실 것입니다.

코드

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        // 11861 Maximal Area 플레 5 히스토그램이랑 비슷한 것 같음.
        /*
        이해하기 쉽게 예시를 들면,
        4
        3 5 1 4 를 입력한다면 각 막대기의 높이는 3514입니다. 그러나 이 문제는 면적을 구하는 문제입니다.
        참고로, 직 사각형을 만들 때에는 기준이 되는 최소 높이를 항상 고려해야합니다.
        따라서, 가장 큰 직사각형의ㅣ 높이는 3이고 너비는 2이게 되는 것입니다. (막대1+2 합쳤다고 보면됨)
        참고, 막대 1과 막대 2는 말 그대로 첫 번째, 두 번째 막대입니다.
        따라서, 막대 1: 높이 3, 막대 2: 높이 5 라서 두개를 결합해서 만들었다고 보시면 됩니다.
        -->  가장 큰 직사각형을 만들기 위해서는 두 막대 중 최소 높이인 3을 기준으로 직사각형의 높이를 결정해야 합니다.
        그렇지 않으면 직사각형의 범위가 높이 3을 넘어서게 되어 더 큰 면적을 구할 수 없습니다.
        그러므로 높이가 3인 직사각형을 결합한 직사각형은 아래와 같은 모양이 됩니다
        ㅁ ㅁ
        ㅁ ㅁ
        ㅁ
        따라서 아래로 #이 3개 가로로 #이 2개이니까 3 * 2 = 6 입니다.
        */
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        int[] histogram = new int[n];
        String[] str = br.readLine().split(" ");

        for (int i = 0; i < n; i++) {
            histogram[i] = Integer.parseInt(str[i]);
        }

        long maxArea = getMaxArea(histogram, n);
        System.out.print(maxArea);
    }

    public static long getMaxArea(int[] histogram, int n) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;

        for (int i = 0; i < n; i++) { //히스토그램의 막대들을 반복함
            // stack에서 top에 있는 막대의 높이가 현재 막대보다 크다면,
            // 계속 직사각형의 가능한 면적을 계산하고 stack에서 높이를 제거
            while (!stack.empty() && histogram[stack.peek()] > histogram[i]) {
                int height = histogram[stack.pop()]; // stack에서 top의 높이를 가져옵니다.
                int width = stack.empty() ? i : i - stack.peek() - 1; // 직사각형의 너비를 계산합니다.
                maxArea = Math.max(maxArea, (long) width * height); // 현재까지 계산한 직사각형 중에서 가장 큰 면적을 저장합니다.
            }
            stack.push(i); // 막대 인덱스를 stack 에 추가해줍니다
        }

        // 모든 막대들을 loop 한 후에, stack 에 남은 나머지 막대들에 대해서도 직사각형의 면적을 계산합니다
        while (!stack.empty()) {
            int height = histogram[stack.pop()]; // stack에서 top의 높이를 가져옵니다.
            int width = stack.empty() ? n : n - stack.peek() - 1; // 직사각형의 너비를 계산합니다.
            maxArea = Math.max(maxArea, (long) width * height); // 현재까지 계산한 직사각형 중에서 가장 큰 면적을 저장합니다.
        }

        return maxArea;
    }
}