[Leetcode] 85. Maximal Rectangle (C++)

문제

85. Maximal Rectangle

코드

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if(matrix.empty()){
            return 0;
        }
        int maxRec = 0;
        vector<int> height(matrix[0].size(), 0);
        for(int i = 0; i < matrix.size(); i++){
            for(int j = 0; j < matrix[0].size(); j++){
                if(matrix[i][j] == '0'){
                    height[j] = 0;
                }
                else{
                    height[j]++;
                }
            }
            maxRec = max(maxRec, largestRectangleArea(height));
        }
        return maxRec;
    }

    int largestRectangleArea(vector<int> &height) {
        stack<int> s;
        height.push_back(0);
        int maxSize = 0;
        for(int i = 0; i < height.size(); i++){
            if(s.empty() || height[i] >= height[s.top()]){
                s.push(i);
            }
            else{
                int temp = height[s.top()];
                s.pop();
                maxSize = max(maxSize, temp * (s.empty() ? i : i - 1 - s.top()));
                i--;
            }
        }
        return maxSize;
    }
};

접근

2차원 배열이 주어지지만 이를 row마다 하나의 히스토그램으로 볼 수 있다. row가 증가하는 방향으로 값을 0 혹은 누적하다 보면 히스토그램의 높이와 같아지게 된다. 따라서 한 줄을 기준으로 최대 넓이를 구하다 보면 전체 2차원 배열에서의 직사각형 넓이의 최대 값이 나올 것이다. 각 row마다의 최대 값은 이전 포스트에서 찾아볼 수 있다. 함수 largestRectangleArea는 이를 활용한 함수이다.