[LeetCode] 85. Maximal Rectangle

문제 URL : https://leetcode.com/problems/maximal-rectangle/

Maximal Rectangle - LeetCode

 

문제 접근법 : 

2차원 배열에서 가장큰 직사각형을 찾는문제인데

백준의 6549번문제 히스토그램의 가장 큰 직사각형 문제의 확장판입니다.

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

6549번: 히스토그램에서 가장 큰 직사각형

 

이문제를 풀지 않으셨다면 풀기 어려울겁니다.

 

문제 접근법을 설명하자면 세로열에서 아래에서 위로 해도 상관없고

위에서 아래로 탐색을 해도 상관없습니다. 연속으로 이어지는 1을 이용하여 

matrix의 열의 사이즈만큼 새로운 배열을 만들어 저장후

히스토그램의 가장 큰직사각형 문제로 이용하셔서 풀면 됩니다.

이문제는 여러가지 알고리즘이 존재하고 분할정복, 스택, 세그먼트트리등 다양하게 풀수있습니다.

 

소스코드 : 

class Solution {
public:
int getRect(vector<int>&v){
    vector<int> st;
    int res=0;
    for(int i=0;i<v.size();i++){
        while(!st.empty()&&v[st.back()]>=v[i]){
            int j =st.back();
            st.pop_back();
            int width=st.empty()?i:i-st.back()-1;
            res = max(res,width*v[j]);
        }
        st.push_back(i);
    }

    return res;
}
int maximalRectangle(vector<vector<char>>& matrix) {
    int n=matrix.size();
    int m = matrix[0].size();
    vector<int> v(m+1);
    int res=0;
    for(int i=0;i<n;i++){
        for(int j=0;j<m;j++){
            v[j]+=(matrix[i][j]=='1'?1:-v[j]);
        }
        res=max(res,getRect(v));
    }
    return res;
}
};

궁금한점 혹은 모르는점 어떤 질문이든 댓글은 언제나 환영입니다.