Maximal Rectangle — Histogram Stack on Each Row

# Python
def maximalRectangle(matrix):
    if not matrix: return 0
    m, n = len(matrix), len(matrix[0])
    heights = [0]*n; ans = 0
    for row in matrix:
        for j in range(n):
            heights[j] = heights[j]+1 if row[j]=='1' else 0
        # Largest rectangle in histogram
        h = [0]+heights+[0]; stack = [0]
        for i in range(1, len(h)):
            while h[stack[-1]] > h[i]:
                ht = h[stack.pop()]
                w = i - stack[-1] - 1
                ans = max(ans, ht*w)
            stack.append(i)
    return ans

// Java
public int maximalRectangle(char[][] matrix) {
    if (matrix.length==0) return 0;
    int n=matrix[0].length, ans=0; int[] heights=new int[n];
    for (char[] row : matrix) {
        for (int j=0;j<n;j++) heights[j]=(row[j]=='1')?heights[j]+1:0;
        ans=Math.max(ans,largestRect(heights));
    }
    return ans;
}
int largestRect(int[] h) {
    Deque<Integer> st=new ArrayDeque<>(); int ans=0;
    for (int i=0;i<=h.length;i++) {
        int cur=(i==h.length)?0:h[i];
        while (!st.isEmpty()&&h[st.peek()]>cur) {
            int height=h[st.pop()];
            int width=st.isEmpty()?i:i-st.peek()-1;
            ans=Math.max(ans,height*width);
        }
        st.push(i);
    }
    return ans;
}