[LeetCode] Maximal Rectangle

Link : http://oj.leetcode.com/problems/maximal-rectangle/

More information:
http://dp2.me/blog/?p=482

Thanks for your help. --> 无齿的兔子, 鹿杖客

 
#include <iostream>
#include <vector>

class Solution {
    public:
    int maximalRectangle(std::vector<std::vector<char> > &matrix) {
        int n = matrix.size();
        if(n==0) return 0;
        int m = matrix[0].size();
        if(m==0) return 0;
        std::vector<int> height(m, 0);
        std::vector<int> left(m, 0);
        std::vector<int> right(m, 0);
        int maxArea = 0;
        for(int i=0; i<n; i++)
        {
            for(int j=0; j<m; j++)
            {
                height[j] = (matrix[i][j]=='1')? height[j]+1 : 0;
                left[j] = j;
                while(left[j]>0 && height[left[j]-1]>=height[j])
                left[j] = left[left[j]-1];
            }
            for(int j=m-1; j>=0; j--)
            {
                right[j] = j;
                while(right[j]<m-1 && height[j]<=height[right[j]+1])
                right[j] = right[right[j]+1];
            }
            for(int j=0; j<m; j++)
            maxArea = std::max(maxArea, (right[j]-left[j]+1)*height[j]);
        }
        return maxArea;
    }
};