Lagest Rectangle In Histogram [Java]

아래 문제를 풀때 사용한 알고리즘 이다.

 

https://www.codetree.ai/ko/trails/complete/curated-cards/test-max-area-of-positive-rectangle/description

양수 직사각형의 최대 크기 설명 | 코드트리

 

 

해당 이차원 배열에서 양수로만 이루어진 직사각형을 찾아야 할때 각 행을 읽어오면서 누적된 양수를 기록해 준다.

for i <- 0 to 4
    if (n>0) height++
    else height = 0

 

 

i = 0 일때 height = [1, 0, 1, 0, 1]
i = 1 일때 height = [2, 1, 2, 0, 2]
i = 2 일때 height = [3, 2, 3, 1, 0] // 음수가 입력되면 0으로 값을 저장한다
i = 3 일때 height = [4, 0, 4, 2, 1]

 

각 행에 들어있는 숫자를 히스토그램이라고 생각하면 막대 형태로 지금까지 누적된 양수가 몇개인지 알 수 있다. 

행을 읽어올 때 마다 아래 함수를 실행해 주면서 Math.max를 사용해 주면 최대값을 구할 수 있게된다

 

 

 

Stack을 이용한 히스토그램 높이 

import java.util.*;

public class Main {
    public static void main(String[] args) {
        // 예제 히스토그램 높이: [2, 1, 4, 5, 1, 3, 3]
        long[] height = {2, 1, 4, 5, 1, 3, 3};
        System.out.println(getMaxArea(height)); // 출력: 8
    }

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

        for (int i = 0; i <= n; i++) {
            // 마지막에 0을 넣어 스택에 남은 모든 막대를 처리
            long h = (i == n) ? 0 : height[i]; 

            while (!stack.isEmpty() && height[stack.peek()] >= h) {
                long heights = height[stack.pop()];
                long width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, heights * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}

 

이전 막대가 현재 막대보다 높을 경우 넓이는 계산해 준다. 그렇지 않은 경우에는 스택에 push해 주며 높이가 더 낮은 막대가 나올때 까지 반복문을 실행해 준다.