b6549. 히스토그램에서 가장 큰 직사각형

 

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

 

 

 

히스토그램에서 가장 큰 직사각형의 넓이를 구하는 문제다. 스택을 써서 아주 풀었다.
히스토그램은 막대들로 이루어진 그래프 같은 건데,
이 막대들을 조합해서 최대한 큰 직사각형을 만들고 그 넓이를 구하는 게 목표다.

먼저 입력으로 막대 개수와 각 막대의 높이를 받아오는데, 
입력이 0이면 종료한다. 
그렇지 않으면 각 히스토그램에 대해 최대 직사각형의 넓이를 계산한다. 
계산의 핵심은 바로 getMaxRectangleArea라는 메서드다.

여기서 스택을 활용해 최대넓이를 갱신한다.

스택에는 막대들의 인덱스를 저장하는데,

현재 막대의 높이가 이전 막대들보다 낮아지면 

스택에서 하나씩 꺼내며 직사각형의 넓이를 계산한다.

꺼낸 막대의 높이를 기준으로 넓이를 구하고,

이걸 최대 넓이와 비교해 갱신한다.

스택이 비어 있으면 막대 하나로 구성된 넓이가 되고,

스택에 값이 남아 있으면 이전 막대들과의 거리를 이용해 너비를 계산한다.

탐색이 끝난 뒤에도 스택에 남아 있는 값들을 처리해 준다.

이렇게 함으로써 히스토그램의 모든 막대를 기준으로

가능한 최대 직사각형을 놓치지 않고 찾아낼 수 있었다.

그리고 이 과정은 높이를 한 번씩만 확인하기 때문에 매우 빠르다.

 

 

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

public class b6549 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        while (true) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int n = Integer.parseInt(st.nextToken());
            if (n == 0) break;
            int[] heights = new int[n];
            for (int i = 0; i < n; i++) {
                heights[i] = Integer.parseInt(st.nextToken());
            }
            System.out.println(getMaxRectangleArea(heights));
        }
    }

    private static long getMaxRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        long maxArea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (!stack.isEmpty() && heights[stack.peek()] > heights[i]) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : (i - stack.peek() - 1);
                maxArea = Math.max(maxArea, (long) height * width);
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty() ? heights.length : (heights.length - stack.peek() - 1);
            maxArea = Math.max(maxArea, (long) height * width);
        }
        return maxArea;
    }
}