首页 > 其他 > 详细

leetcode_85

时间:2017-12-15 14:33:00      阅读:231      评论:0      收藏:0      [点我收藏+]
class Solution(object):
    def maximalRectangle(self, matrix):
        """
        :type matrix: List[List[str]]
        :rtype: int
        """
        if len(matrix) == 0: return 0   # 在这里被 wa 一次
        n, m = len(matrix), len(matrix[0])
        mt = map(lambda x: map(int, x), matrix)
        height, maxArea = [0 for i in range(0, m+1)], 0
        stack = []
    
        for i in range(0, n):
            for j in range(1, m+1):
                height[j] = (height[j] + 1) *  mt[i][j-1]
                
            level, tmp = 1, 0
            stack = [(1,m)]
            while True:
                if len(stack) == 0:
                    break
                tstack = []
                for (wi, wj) in stack:
                    for j in range(wi, wj+1):
                        if height[j] >= level:
                            tmp += 1
                        else:
                            if tmp > 0:
                                tstack.append((j-tmp, j-1))
                                maxArea = max(maxArea, tmp* level)
                            tmp = 0
                    if tmp > 0:   # 这里能不能不这么做?代码重复啊
                        tstack.append((wj-tmp+1, wj))
                        maxArea = max(maxArea, tmp* level)
                        tmp = 0
                            
                stack = tstack
                level += 1
        return maxArea    
                
if __name__ == __main__:
    a = Solution()
    print a.maximalRectangle([["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]])

         一开始准备用二维 DP 来做,但是发现不好写。看了别人用了 height 数组解决此题,后面写了上述题解。        

 

leetcode_85

原文:http://www.cnblogs.com/tmortred/p/8042753.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!