99클럽 코테 스터디 22일차 TIL / Maximal Rectangle(Leetcode)

오늘의 학습 키워드

   - 알고리즘

   - 스택

   - DP

   - 구현

공부한 내용 본인의 언어로 정리하기

https://leetcode.com/problems/maximal-rectangle/description/

dp를 응용하는 문제를 풀었다. 아이디어가 떠오르지 않아 결국 다른 사람의 코드를 참고했다.

 

풀이는 다음과 같다.

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }

        int maxArea = 0;
        int[] heights = new int[matrix[0].length];

        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == '1') {
                    heights[j] += 1;
                } else {
                    heights[j] = 0;
                }
            }
            maxArea = Math.max(maxArea, getLargestSize(heights));
        }

        return maxArea;
    }

    private int getLargestSize(int[] heights) {
        ArrayDeque<Integer> stack = new ArrayDeque<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            int height = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && height < heights[stack.peekLast()]) {
                int h = heights[stack.pollLast()];
                int width = stack.isEmpty() ? i : i - stack.peekLast() - 1;
                maxArea = Math.max(maxArea, h * width);
            }
            stack.addLast(i);
        }

        return maxArea;
    }
}