class Solution {

public:

    int maximalRectangle(vector<vector<char> > &matrix) {

        int ret = ;;

        if(matrix.empty() || matrix[].empty())

            return ret;

        int m = matrix.size();

        int n = matrix[].size();

        for(int i = ; i < matrix.size(); i ++)

        {

            vector<int> height(n, );

            for(int j = ; j < n; j ++)

            {

                int r = i;

                while(r >=  && matrix[r][j] == '')

                {

                    height[j] ++;

                    r --;

                }

            }

            ret = max(ret, largestRectangleArea(height));

        }

        return ret;

    }

    int largestRectangleArea(vector<int> &height) {

        if(height.empty())

            return ;

        int result = ;

        stack<int> s;   //elements in stack s are kept in ascending order

        int ind = ;

        while(ind < height.size())

        {

            if(s.empty() || height[ind]>=s.top())

            {

                s.push(height[ind]);

            }

            else

            {

                int count = ;  //pop count

                while(!s.empty() && height[ind]<s.top())

                {

                    int top = s.top();

                    s.pop();

                    count ++;

                    result = max(result, count*top);

                }

                for(int i = ; i <= count; i ++)

                    s.push(height[ind]);    //push count+1 times

            }

            ind ++;

        }

        //all elements are in stack s, and in ascending order

        int count = ;

        while(!s.empty())

        {

            count ++;

            int top = s.top();

            s.pop();

            result = max(result, count*top);

        }

        return result;

    }

};