Python Increasing Stack


  • 0

    Utilize the property of a increasing stack:

    element in an array with the index between stack[i] -- stack[i + 1] should all be greater than array[i + 1]

    class Solution(object):
        def maximalRectangle(self, matrix):
            if not matrix:
                return 0
            h, w = len(matrix), len(matrix[0])
            height = [ 0 for i in xrange(w + 1) ]
            a = 0
            for i in xrange(h):
                for j in xrange(w):
                    if matrix[i][j] == '1':
                        height[j] += 1
                    else:
                        height[j] = 0
                s = []
                for ii in xrange(len(height)):
                    while s and height[s[-1]] > height[ii]:
                        hh = height[s.pop()]
                        ww = ii if not s else ii - s[-1] - 1
                        a = max(a, hh * ww)
                    s.append(ii)
            return a
    

Log in to reply
 

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