13 lines in python beats 97%


  • 0
    G

    The theory is get maximal histogram areas by rows.

    class Solution(object):
    def maximalRectangle(self, matrix):
        res, histRow = 0, ([0 for _ in matrix[0]]) if matrix else None
        for rowNums in matrix:
            stk = []
            for c, num in enumerate(rowNums):
                histRow[c] = (histRow[c]+1) if num == '1' else 0
            for i, n in enumerate(histRow+[0]):
                while stk and histRow[stk[-1]] > n:
                    h = histRow[stk.pop()]
                    res = max(res, h * ((i - stk[-1] - 1) if stk else i))
                stk.append(i)
        return res

  • 0
    K

    @geeti said in 13 lines in python beats 97%:

    The theory is get maximal histogram areas by rows.

    class Solution(object):
    def maximalRectangle(self, matrix):
        res, histRow = 0, ([0 for _ in matrix[0]]) if matrix else None
        for rowNums in matrix:
            stk = []
            for c, num in enumerate(rowNums):
                histRow[c] = (histRow[c]+1) if num == '1' else 0
            for i, n in enumerate(histRow+[0]):
                while stk and histRow[stk[-1]] > n:
                    h = histRow[stk.pop()]
                    res = max(res, h * ((i - stk[-1] - 1) if stk else i))
                stk.append(i)
        return res

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.