[LeetCode] 85. Maximal Rectangle

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

Leetcode - Maximal Rectangle

문제 유형 : 히스토그램, 스택, 다이나믹 프로그래밍

문제 난이도 : Hard

 

문제

Given a rows x cols binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.

 

rows x cols크기의 이진 행렬이 주어진다.  1로만 이루어진 가장 큰 직사각형을 찾아서 그 크기를 반환하시오.

 

풀이

풀이 1: 다이나믹 프로그래밍(동적계획법)

처음에는 각 자리별로 1로 이어진 왼쪽 끝과 위쪽 끝을 구한 뒤, 크기를 일일이 다 구해서 가장 큰 것을 반환하는 풀이를 했다.

3차원 배열 dp[row][col][0: row, 1: col] = (위쪽 어디서부터 1이 연속되는지 / 왼쪽 어디서부터 1이 연속되는지)를 저장해서,

이 데이터들을 기반으로 만들 수 있는 모든 사각형들의 넓이를 구했고, 이들의 크기들 중 최대값을 갱신시켰다.

 

아래 그림에는 원본 배열과, 현재 1의 연결이 어디서부터 이어져오는지를 표시함을 보이고 있다.

이 방법은 그리 효율적이지 못하다. 풀면서도 불필요한 과정이 있는 듯함을 느꼈다.

일단 TC를 모두 통과하기는 했다.

 

 

풀이 2: 스택을 이용한 히스토그램 풀이

출처: 

https://leetcode.com/problems/maximal-rectangle/solutions/5014890/faster-lesser-detailed-explaination-stack-height-step-by-step-explaination-python-java/

 

height배열에는 세로로 1이 얼마나 쌓여있는지를 나타낸다.

행렬을 열별로 순회하면서, 다음 과정을 따른다: 

1. heights[i]에 row[i]가 '1'이면 1을 누적시키고, 아니면 0으로 초기화한다.
2. 히스토그램 바 인덱스를 저장하기 위해 스택을 만든다.
3. heights배열을 순회하면서, 다음의 과정을 따른다:
   1. 스택의 맨 위의 값을 pop하여 불러온다. 높이를 heights[스택에서 뺀 값]으로 한다.
   2. 너비는 스택이 현재 빈 경우, i로, 아니면 i - 현재 스택의 맨 위 값 - 1로 한다.
   3. 최대 넓이를 노비 * 높이와 비교하여 업데이트한다.
   4. 스택에 i를 푸시한다.
4. 최대 넓이를 반환한다.

아래는 시각화이다. 이 풀이는 높이를 누적시켜서 히스토그램의 형태로 만드는 아이디어가 핵심인 듯 하다.

풀이에서 감탄이 안 나올수가 없다..

 

 

코드

C++ : 풀이 1(동적계획법)

class Solution {
public:
    int getArea(int row, int col, vector<vector<vector<int>>>& dp) {
        int maxSize = 0;
        int rowRoot = dp[row][col][0];
        int colRoot = dp[row][col][1];

        if (rowRoot == -1 || colRoot == -1)
            return 0;

        for (int k = row; k >= rowRoot; --k) {
            colRoot = max(colRoot, dp[k][col][1]);
            maxSize = max(maxSize, (col - colRoot + 1) * (row - k + 1));
        }
        return maxSize;
    }

    int maximalRectangle(vector<vector<char>>& matrix) {
        int rows = matrix.size();
        int cols = matrix[0].size();

        int ans;
        // dp[row][col][row_or_col] = root from left or upper
        vector<vector<vector<int>>> dp(rows, vector<vector<int>>(cols, vector<int>(2, -1)));
        // last 0 = rowStack root idx
        // last 1 = colStack root idx
        dp[0][0][0] = matrix[0][0] == '1'? 0 : -1;
        dp[0][0][1] = matrix[0][0] == '1'? 0 : -1;

        ans = getArea(0, 0, dp);

        for(int i = 1; i < rows; i++) {
            if(matrix[i][0] == '1') {
                if(dp[i-1][0][0] != -1) dp[i][0][0] = dp[i-1][0][0];
                else dp[i][0][0] = i;

                dp[i][0][1] = 0;
            }

            ans = max(ans, getArea(i, 0, dp));
        }

        for(int j = 1; j < cols; j++) {
            if(matrix[0][j] == '1') {
                if(dp[0][j-1][1] != -1) dp[0][j][1] = dp[0][j-1][1];
                else dp[0][j][1] = j;

                dp[0][j][0] = 0;
            }

            ans = max(ans, getArea(0, j, dp));
        }

        for(int i = 1; i < rows; i++) {
            for(int j = 1; j < cols; j++) {
                if(matrix[i][j] == '1') {
                    if(dp[i-1][j][0] != -1) dp[i][j][0] = dp[i-1][j][0];
                    else dp[i][j][0] = i;

                    if(dp[i][j-1][1] != -1) dp[i][j][1] = dp[i][j-1][1];
                    else dp[i][j][1] = j;
                }

                ans = max(ans, getArea(i, j, dp));
            }
        }

        return ans;
    }
};

 

 

C++: 풀이 2(스택과 히스토그램)

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty() || matrix[0].empty())
            return 0;

        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> heights(cols + 1, 0); // Include an extra element for easier calculation
        int maxArea = 0;

        for (const auto& row : matrix) {
            for (int i = 0; i < cols; i++) {
                heights[i] = (row[i] == '1') ? heights[i] + 1 : 0;
            }

            // Calculate max area using stack-based method
            stack<int> stk;
            for (int i = 0; i < heights.size(); i++) {
                while (!stk.empty() && heights[i] < heights[stk.top()]) {
                    int h = heights[stk.top()];
                    stk.pop();
                    int w = stk.empty() ? i : i - stk.top() - 1;
                    maxArea = max(maxArea, h * w);
                }
                stk.push(i);
            }
        }

        return maxArea;
    }
};