leetcode 85 - Maximal Rectangle

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

풀이

모든 시작, 끝에 대해 사각형을 비교해보면 $O(n^4)$만에 찾을 수 있다. 여기서 조금씩 개선해보자.

matrix[i][j]가 있을 때 모든 i, j 쌍에 대해서 비교하지 말고, 아래와 같이 높이 배열을 사용하면 개선할 수 있다.

height[i][j] = matrix[i][j]부터 위에(같은 열) 존재하는 연속된 1의 개수

이렇게 height[i][j]를 정의하면 모든 $n^2$개의 행의 쌍이 아닌 고정된 행에서만 비교하면 되기 때문에 $O(n^3)$만에 구할 수 있다.

 

i는 $O(n)$으로 줄였지만 여전히 height 하나의 행에서 최대 직사각형을 찾기 위해 $O(n^2)$이 필요하다. 모든 인덱스에 대해서 자기가 최대 높이일 때 가능한 최대 너비를 구해서 넓이를 비교하는 시간이다. 여기서는 최대 직사각형의 후보가 될 수 없는 불필요한 연산을 제거하면서 시간을 줄일 수 있다.

임의의 인덱스 i를 기준으로 인덱스는 작은데 높이는 더 큰 인덱스 j가 있을 때, j는 i보다 큰 인덱스 k와 합쳐져서 직사각형을 만들 수 없다. j와 k 사이에 j보다 높이가 작은 i가 있기 때문이다. 반대로 j의 높이가 i보다 작은 경우라면 k와 합쳐져서 직사각형을 만들 수 있다. 

 

이런 인사이트를 가지고 구현을 할 수 있다.

이전 인덱스들의 높이를 오름차순으로 유지하면서 현재 인덱스의 높이를 가장 큰 값으로 갱신할 수 있도록 인덱스를 담는 스택 자료구조를 사용한다. 현재 인덱스의 높이보다 큰 값을 가지는 이전 인덱스들은 스택에서 제거되는데 이때 이 높이로 가질 수 있는 최대 넓이 직사각형을 구해야 한다. 그러려면 너비를 구해야 한다. 가능한 최대 너비의 오른쪽 끝 부분은 현재 인덱스이다. 해당 인덱스를 기준으로 오른쪽 방향으로 가장 먼저 등장하는 해당 높이보다 작은 인덱스이기 때문이다. 최대 너비의 왼쪽 끝 인덱스는 스택에서 두 번째 위에 있는 값이다. 이 값이 해당 인덱스를 기준으로 왼쪽 방향으로 가장 먼저 등장하는 높이가 작은 인덱스이기 때문이다. 

 

이렇게 하면 모든 인덱스에 대해 스택에 push, pop 명령이 한 번씩 발생하여 $O(n)$만에 구할 수 있다. 이를 height의 모든 i에 대해 구해야 하므로 총 시간 복잡도는 $O(n^2)$가 된다.

 

 

코드

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if(matrix.size() == 0 || matrix[0].size() == 0) return 0;
        int n = matrix.size(), m = matrix[0].size();
        vector<int> height(m+1);
        
        int ans = 0;
        for(int i = 0; i < n; i++) {
            stack<int> st;
            for(int j = 0; j <= m; j++) {
                if(j == m || matrix[i][j] == '0') height[j] = 0;
                else height[j]++;

                while (!st.empty() && height[st.top()] >= height[j]) {
                    int _height = height[st.top()];
                    st.pop();
                    int _width = st.empty() ? j : j - st.top() - 1;
                    ans = max(ans, _width * _height);
                }
                st.push(j);
            }
        }
        
        return ans;
    }
};