85. maximal rectangle

class (object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if len(matrix)==0 or len(matrix[0])==0:
            return 0
        m,n = len(matrix), len(matrix[0])
        height = [0]*n
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j]=='1':
                    height[j] = int(matrix[i][j]) + height[j]
                else:
                    height[j] = 0
            ans = max(ans, find(height))
        return ans
    
    
def find(nums):
    if len(nums)==0:
        return 0
    if len(nums)==1:
        return nums[0]
    nums.append(0)
    ans = 0
    st = []
    i = 0
    while i<len(nums):
        if len(st)==0 or nums[st[-1]]<=nums[i]:
            st.append(i)
            i += 1
        else:
            temp = st.pop(-1)
            area = nums[temp]*(i-1-st[-1]) if len(st)>0 else nums[temp]*i
            ans = max(ans, area)
    nums.pop(-1)
    return ans