Maximal Rectangle

class Solution {
public:
    int maximalRectangle(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<int> heights(n, 0);
        int best = 0;
        for (int r = 0; r < m; ++r) {
            for (int c = 0; c < n; ++c)
                heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
            best = max(best, largestRectangle(heights));
        }
        return best;
    }
private:
    int largestRectangle(vector<int>& h) {
        h.push_back(0);
        stack<int> st;
        int best = 0;
        for (int i = 0; i < (int)h.size(); ++i) {
            while (!st.empty() && h[st.top()] > h[i]) {
                int top = st.top(); st.pop();
                int width = st.empty() ? i : i - st.top() - 1;
                best = max(best, h[top] * width);
            }
            st.push(i);
        }
        h.pop_back();
        return best;
    }
};

func maximalRectangle(matrix [][]byte) int {
    if len(matrix) == 0 {
        return 0
    }
    m, n := len(matrix), len(matrix[0])
    heights := make([]int, n)
    best := 0
    for r := 0; r < m; r++ {
        for c := 0; c < n; c++ {
            if matrix[r][c] == '1' {
                heights[c]++
            } else {
                heights[c] = 0
            }
        }
        if a := largestRectangleArea(heights); a > best {
            best = a
        }
    }
    return best
}

func largestRectangleArea(h []int) int {
    h = append(h, 0)
    defer func() { h = h[:len(h)-1] }()
    var st []int
    best := 0
    for i := 0; i < len(h); i++ {
        for len(st) > 0 && h[st[len(st)-1]] > h[i] {
            top := st[len(st)-1]
            st = st[:len(st)-1]
            width := i
            if len(st) > 0 {
                width = i - st[len(st)-1] - 1
            }
            if h[top]*width > best {
                best = h[top] * width
            }
        }
        st = append(st, i)
    }
    return best
}

from typing import List

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix:
            return 0
        m, n = len(matrix), len(matrix[0])
        heights = [0] * n
        best = 0
        for r in range(m):
            for c in range(n):
                heights[c] = heights[c] + 1 if matrix[r][c] == '1' else 0
            best = max(best, self._largestRectangle(heights))
        return best

    def _largestRectangle(self, h: List[int]) -> int:
        h.append(0)
        st: List[int] = []
        best = 0
        for i in range(len(h)):
            while st and h[st[-1]] > h[i]:
                top = st.pop()
                width = i if not st else i - st[-1] - 1
                if h[top] * width > best:
                    best = h[top] * width
            st.append(i)
        h.pop()
        return best

function maximalRectangle(matrix) {
    if (!matrix.length) return 0;
    const m = matrix.length, n = matrix[0].length;
    const heights = new Array(n).fill(0);
    let best = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
        }
        best = Math.max(best, largestRectangle(heights));
    }
    return best;
}

function largestRectangle(h) {
    h.push(0);
    const st = [];
    let best = 0;
    for (let i = 0; i < h.length; i++) {
        while (st.length && h[st[st.length - 1]] > h[i]) {
            const top = st.pop();
            const width = st.length === 0 ? i : i - st[st.length - 1] - 1;
            if (h[top] * width > best) best = h[top] * width;
        }
        st.push(i);
    }
    h.pop();
    return best;
}

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix.length == 0) return 0;
        int m = matrix.length, n = matrix[0].length;
        int[] heights = new int[n];
        int best = 0;
        for (int r = 0; r < m; r++) {
            for (int c = 0; c < n; c++) {
                heights[c] = matrix[r][c] == '1' ? heights[c] + 1 : 0;
            }
            best = Math.max(best, largestRectangle(heights));
        }
        return best;
    }

    private int largestRectangle(int[] heights) {
        int n = heights.length;
        int[] h = new int[n + 1];
        System.arraycopy(heights, 0, h, 0, n);
        h[n] = 0;
        Deque<Integer> st = new ArrayDeque<>();
        int best = 0;
        for (int i = 0; i < h.length; i++) {
            while (!st.isEmpty() && h[st.peek()] > h[i]) {
                int top = st.pop();
                int width = st.isEmpty() ? i : i - st.peek() - 1;
                if (h[top] * width > best) best = h[top] * width;
            }
            st.push(i);
        }
        return best;
    }
}

function maximalRectangle(matrix: string[][]): number {
    if (!matrix.length) return 0;
    const m = matrix.length, n = matrix[0].length;
    const heights: number[] = new Array(n).fill(0);
    let best = 0;
    for (let r = 0; r < m; r++) {
        for (let c = 0; c < n; c++) {
            heights[c] = matrix[r][c] === '1' ? heights[c] + 1 : 0;
        }
        best = Math.max(best, largestRectangle(heights));
    }
    return best;
}

function largestRectangle(h: number[]): number {
    h.push(0);
    const st: number[] = [];
    let best = 0;
    for (let i = 0; i < h.length; i++) {
        while (st.length && h[st[st.length - 1]] > h[i]) {
            const top = st.pop()!;
            const width = st.length === 0 ? i : i - st[st.length - 1] - 1;
            if (h[top] * width > best) best = h[top] * width;
        }
        st.push(i);
    }
    h.pop();
    return best;
}