Using stack, strengthen the previous problem


  • 0

    1.0 Time O(n^2) Space O(n^2)

        int maximalRectangle(vector<vector<char>>& matrix) {
            if(matrix.size() == 0)
                return 0;
            int m = matrix.size(), n = matrix[0].size(), maxArea = 0;
            vector<vector<int>> num(m, vector<int>(n + 1, 0));
            for(auto i = 0; i < m; i ++)
            {
                stack<int> s;
                for(auto j = 0; j <= n;)
                {
                    if(j != n && matrix[i][j] == '1')
                        num[i][j] = 1 + (i == 0 ? 0: num[i - 1][j]);
                    if(s.empty() || num[i][j] >= num[i][s.top()])
                            s.push(j++);
                    else
                    {
                        int top = s.top();
    			        s.pop();
    			        maxArea = max(maxArea, num[i][top] * (s.empty() ? j: j - s.top() - 1));
                    }
                }
            }
            return maxArea;
        }
    

    1.1 time O(n^2) Space(n)

        int maximalRectangle(vector<vector<char>>& matrix) {
            if(matrix.size() == 0)
                return 0;
            int m = matrix.size(), n = matrix[0].size(), maxArea = 0;
            vector<int> num(n + 1, 0);
            for(auto i = 0; i < m; i ++)
            {
                stack<int> s;
                bool cur = false;
                for(auto j = 0; j <= n;)
                {
                    if(!cur)
                        if(j != n && matrix[i][j] == '1')
                            num[j] = 1 + num[j];
                        else
                            num[j] = 0;
                    if(s.empty() || num[j] >= num[s.top()])
                    {
                            s.push(j++);
                            cur = false;
                    }
                    else
                    {
                        int top = s.top();
    			        s.pop();
    			        maxArea = max(maxArea, num[top] * (s.empty() ? j: j - s.top() - 1));
    			        cur = true;
                    }
                }
            }
            return maxArea;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.