Jianbo Dai's

lc085.最大矩形

 
  • Mar 06, 2021

题目链接

啊这个，我之前面试的时候倒是做了一个最大正方形，一下就做出来了的。现在这个思考一下感觉和“lc042接雨水”有点像。在那道题里面用到了暴力算法和单调栈，这道题里也是。在做这道题之前，我先做了一下lc84最大矩形，因为那个题里的思路能够很好地用到本题上面。简而言之，我们扫描每一行，用类似前缀和的思想记录下每个位置到当前为止连续1的个数，对于每一行，我们再将这一行看作底，去求若干以该行为底的柱形中所包含的最大矩形有多大。将上述计算用在每一行中找到最终的答案。

后续发现用“哨兵”避免分类讨论时没必要用俩，只要用一个就行并且要将stack里的初始元素设为-1即指向新加入的末尾哨兵。这样在遍历时就没必要从1开始而是自然地从0开始即可。

这个算法的时间复杂度是O（NM），空间复杂度是O（N）。

python:

class Solution1:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        heights = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "0":
                    heights[j] = 0
                else:
                    heights[j] += 1
            ans = max(ans, self.largestRectangleArea(heights))
        return ans
        
    def largestRectangleArea(self, heights) -> int:
        heights = [0] + heights + [0]
        size = len(heights)
        stack = [0]
        res = 0
        for i in range(1, size):
            while heights[i] < heights[stack[-1]]:
                cur_height = heights[stack.pop()]
                cur_width = i - stack[-1] - 1
                res = max(res, cur_height * cur_width)
            stack.append(i)
        return res

class Solution2:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m = len(matrix)
        if m == 0:
            return 0
        n = len(matrix[0])
        heights = [0] * n
        ans = 0
        for i in range(m):
            for j in range(n):
                if matrix[i][j] == "0":
                    heights[j] = 0
                else:
                    heights[j] += 1
            ans = max(ans, self.largestRectangleArea(heights))
        return ans
        
    def largestRectangleArea(self, heights) -> int:
        heights = heights + [0]
        size = len(heights)
        stack = [-1]
        res = 0
        for i in range(size):
            while heights[i] < heights[stack[-1]]:
                cur_height = heights[stack.pop()]
                cur_width = i - stack[-1] - 1
                res = max(res, cur_height * cur_width)
            stack.append(i)
        return res
Search