Maximal Rectangle

Maximal Rectangle

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

-------------------------------------------- think ------------------------------------------------
similar to max histgram question

----------------------------------------------- codes ---------------------------------------------
class Solution {
public:
    int maximalRectangle(vector<vector<char> > &matrix) {
        if (matrix.size() == 0) {
            return 0;
        }
        int max = 0;
        vector<int> hist(matrix[0].size(), 0);
        for (int j = 0; j < matrix.size(); j++) {
            //update hist
            //bug here -> the updating of hist should consider '0' situation!!!
            for (int i = 0; i < matrix[j].size(); i++) {
                if (matrix[j][i] == '0') {
                    hist[i] = 0;
                } else {
                    hist[i] += 1;
                }
            }
            int area = getMaxHist(hist);
            max = max>area?max:area;
        }
        return max;
    }
    int getMaxHist(vector<int> &hist) {
        int max = 0;
        int area;
        stack<int> stk;
        stk.push(-1);
        //bug here -> i should be looped to hist.size()
        for (int i = 0; i <= hist.size(); i++) {
            if (i < hist.size() && (stk.size() == 1 || hist[i] >= hist[stk.top()])) {
                stk.push(i);
                continue;
            }
            while (stk.size() > 1 && (i == hist.size() || hist[i] <= hist[stk.top()])) {
                int height = hist[stk.top()];
                stk.pop();
                area = height * (i - stk.top() - 1);
                max = max>area?max:area;
            }
            stk.push(i);
        }
        return max;
    }
};