Maximal Rectangle [Leetcode]

Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.

Solution: the best solution to this problem I have ever seen is O(mn), which based on the solution to Largest Rectangle in Histogram [see here for explanation, the first algorithm in this post is O(m^2n^2)].

   /*******************************SOLUTION 1***********************************/

class Solution {
public:
    int largestRectangleArea(vector<int> &height) {
        if(height.empty()) return 0;
        //adding a dummy bar with height -1.
        height.push_back(-1);
        int maxSum = 0, n=height.size();
        stack<int> s;
        for(int i=0; i<n; ++i){
            while(!s.empty() && height[i]<height[s.top()]){
                int curIndex = s.top();
                s.pop();
                int numBar = (s.empty()?i:i-s.top()-1);
                maxSum = max(maxSum, height[curIndex]*numBar);
            }
            s.push(i);
        }
        return maxSum;
    }
    
    int maximalRectangle(vector<vector<char> > &matrix) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(matrix.empty() || matrix[0].empty())
            return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<int> heights(cols, 0);
        int maxArea = 0;
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                if(i==0)
                    heights[j]=matrix[0][j]-'0';
                else
                    heights[j] = (matrix[i][j]=='0'?0:heights[j]+1);
            }
            maxArea = max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }
};

   /*******************************SOLUTION 2***********************************/
The time complexity of the following implementation is O(mn^2) and the space requirement is O(mn) [see here for explanation]. If you want a constant space algorithm, you can just delete the two-dimensional heights array, and compute it dynamically, thus the time complexity becomes O(m^2n^2). 

class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        if(matrix.empty() || matrix[0].empty())
            return 0;
        int rows = matrix.size();
        int cols = matrix[0].size();
        vector<vector<int>> heights(rows, vector<int>(cols, 0)); //along the columns
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                if(i==0)
                    heights[0][j]=matrix[0][j]-'0';
                else
                    heights[i][j] = (matrix[i][j]=='0'?0:heights[i-1][j]+1);
            }
        }
        int maxArea = 0;
        for(int i=0; i<rows; ++i){
            for(int j=0; j<cols; ++j){
                if(matrix[i][j]=='0')
                    continue;
                int h = INT_MAX;
                int area = 0;
                for(int k=j; k<cols && matrix[i][k]=='1'; ++k){
                    h = min(h, heights[i][k]);            
                    area = (k-j+1)*h;
                    maxArea = max(maxArea, area);
                }
            }
        }
        return maxArea;
    }
};