[python刷题模板] 子矩阵面积

• • 一、 算法&数据结构
  • • 1. 描述
    • 2. 复杂度分析
    • 3. 常见应用
    • 4. 常用优化
  • 二、 模板代码
  • • 1. 柱状图的最大矩形
    • 2. 最大子矩形
    • 3. 矩形可调整，求最大子矩形

比较特定的题目，要求子矩阵最大面积、柱状图最大矩形面积。做法类似。

1. O(M×N)

1. 最大子矩形面积
2. 柱状图面积
3. 矩阵可以调整的最大子矩形面积

1. 遍历时同时处理求高度。
2. 排序剪枝。

例题: 84. 柱状图中最大的矩形
求出每个以每个柱的高度为高做矩形，所有能有延伸到哪，显然是求左右两边第一个矮于它的柱子。
用单调栈。

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        # 单调栈求出以每个柱子为高，可以左右延伸到哪
        # 也就是求出左右两边第一个矮于当前柱子的柱子，即为边界
        n = len(heights)
        left = [-1] * n
        right = [n] * n
        stack = []
        for i in range(n):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()            
            if stack:
                left[i] = stack[-1]
            stack.append(i)
        stack.clear()
        for i in range(n-1,-1,-1):
            while stack and heights[stack[-1]] >= heights[i]:
                stack.pop()
            if stack:
                right[i] = stack[-1]
            stack.append(i)
        return max(heights[i]*(right[i]-left[i]-1) for i in range(n))            

链接: 85. 最大矩形

相当于把上一题做了m遍，综合求最大。

class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        m,n = len(matrix),len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                matrix[i][j] = int(matrix[i][j])
                if i > 0 and matrix[i][j] == 1:
                    matrix[i][j] = matrix[i-1][j] + 1
            
            left = [-1] * n
            right = [n] * n
            stack = []
            row = matrix[i]
            for j in range(n):
                while stack and row[stack[-1]] >= row[j]:
                    stack.pop()
                if stack:
                    left[j] = stack[-1]
                stack.append(j)
            stack.clear()
            for j in range(n-1,-1,-1):
                while stack and row[stack[-1]] >= row[j]:
                    stack.pop()
                if stack:
                    right[j] = stack[-1]
                stack.append(j)
            ans = max(ans ,max((right[j]-left[j]-1)*row[j] for j in range(n)))

        return ans

链接: [1727. 重新排列后的最大子矩阵](https://leetcode.cn/problems/largest-submatrix-with-rearrangements/

和上题的区别是：每一列都可以任意摆放。
那么不用找管辖的最大区域了，我们来设置最大区域即可。
排序，往高的地方延伸。
单调栈不用做，代码会短一些。

class Solution:
    def largestSubmatrix(self, matrix: List[List[int]]) -> int:
        m,n = len(matrix),len(matrix[0])
        ans = 0
        for i in range(m):
            for j in range(n):
                if i > 0 and matrix[i][j] == 1:
                    matrix[i][j] = matrix[i-1][j] + 1
            
            for j,h in  enumerate(sorted(matrix[i],reverse=True)):
                
                if ans >= h*n:  # 即使后边都是h，数据也不会更新，那就不用继续了。
                    break 
                ans = max(ans,h*(j+1))
        
        return ans

## 三、其他
1) 如果还是卡常数，单调栈可以只走一次，还有前缀和优化，但都是常数优化，去看看官方题解。
## 四、更多例题
- 待补充
## 五、参考链接
- 待补充