剑指OfferII040.矩阵中最大的矩形

---

comments: true edit_url: github /doocs/leetcode/edit/main/lcof2/%E5%89%91%E6%8C%87%20Offer%20II%20040.%20%E7%9F%A9%E9%98%B5%E4%B8%AD%E6%9C%80%E5%A4%A7%E7%9A%84%E7%9F%A9%E5%BD%A2/README.md 剑指 Offer II 040. 矩阵中最大的矩形 题目描述

给定一个由 0 和 1 组成的矩阵 matrix ，找出只包含 1 的最大矩形，并返回其面积。

注意：此题 matrix 输入格式为一维 01 字符串数组。

 

示例 1：

输入：matrix = ["10100","10111","11111","10010"] 输出：6 解释：最大矩形如上图所示。

示例 2：

输入：matrix = [] 输出：0

示例 3：

输入：matrix = ["0"] 输出：0

示例 4：

输入：matrix = ["1"] 输出：1

示例 5：

输入：matrix = ["00"] 输出：0

 

提示：

rows == matrix.lengthcols == matrix[0].length0 <= row, cols <= 200matrix[i][j] 为 '0' 或 '1'

 

注意：本题与主站 85 题相同（输入参数格式不同）：  leetcode /problems/maximal-rectangle/

解法 方法一：单调栈

把每一行视为柱状图的底部，对每一行求柱状图的最大面积即可。

时间复杂度 O ( m n ) O(mn) O(mn)，其中 m m m 表示 m a t r i x matrix matrix 的行数， n n n 表示 m a t r i x matrix matrix 的列数。

Python3 class Solution: def maximalRectangle(self, matrix: List[str]) -> int: if not matrix: return 0 n=len(matrix[0]) res=0 height_row=[0]*n for row in matrix: # 每行作为基座，累计向上的连续历史高度 for j,v in enumerate(row): if v=="1": height_row[j]+=1 else: height_row[j]=0 #说明无基座，不需要累计，历史高度归于0 # res=max(res,self.largestRectangleArea(height_row)) return res def largestRectangleArea(self, heights: List[int]) -> int: n=len(heights) h_left_minid=[0]*n h_right_minid=[n-1]*n st=[] for i,h in enumerate(heights): while st and heights[st[-1]]>h: idx=st.pop() h_right_minid[idx]=i-1 st.append(i) heights_copy=heights[::-1] st = [] for i, h in enumerate(heights_copy): while st and heights_copy[st[-1]] > h: idx = st.pop() h_left_minid[n-1-idx] = n-1-i + 1 st.append(i) return max((r-l+1)*h for h,r,l in zip(heights,h_right_minid,h_left_minid)) Java class Solution { public int maximalRectangle(String[] matrix) { if (matrix == null || matrix.length == 0) { return 0; } int n = matrix[0].length(); int[] heights = new int[n]; int ans = 0; for (var row : matrix) { for (int j = 0; j < n; ++j) { if (row.charAt(j) == '1') { heights[j] += 1; } else { heights[j] = 0; } } ans = Math.max(ans, largestRectangleArea(heights)); } return ans; } private int largestRectangleArea(int[] heights) { int res = 0, n = heights.length; Deque<Integer> stk = new ArrayDeque<>(); int[] left = new int[n]; int[] right = new int[n]; Arrays.fill(right, n); for (int i = 0; i < n; ++i) { while (!stk.isEmpty() && heights[stk.peek()] >= heights[i]) { right[stk.pop()] = i; } left[i] = stk.isEmpty() ? -1 : stk.peek(); stk.push(i); } for (int i = 0; i < n; ++i) { res = Math.max(res, heights[i] * (right[i] - left[i] - 1)); } return res; } } C++ class Solution { public: int h[210]; int l[210], r[210]; int maximalRectangle(vector<string>& matrix) { int n = matrix.size(); if (n == 0) return 0; int m = matrix[0].size(); int ans = 0; stack<int> st; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { h[j] = (matrix[i][j] == '1' ? h[j] + 1 : 0); while (st.size() && h[j] <= h[st.top()]) { ans = max(ans, (j - l[st.top()] - 1) * h[st.top()]); st.pop(); } if (st.size()) l[j] = st.top(); else l[j] = -1; st.push(j); } while (st.size()) { ans = max(ans, (m - 1 - l[st.top()]) * h[st.top()]); st.pop(); } } return ans; } }; Go func maximalRectangle(matrix []string) int { if len(matrix) == 0 { return 0 } n := len(matrix[0]) heights := make([]int, n) ans := 0 for _, row := range matrix { for j, v := range row { if v == '1' { heights[j]++ } else { heights[j] = 0 } } ans = max(ans, largestRectangleArea(heights)) } return ans } func largestRectangleArea(heights []int) int { res, n := 0, len(heights) var stk []int left, right := make([]int, n), make([]int, n) for i := range right { right[i] = n } for i, h := range heights { for len(stk) > 0 && heights[stk[len(stk)-1]] >= h { right[stk[len(stk)-1]] = i stk = stk[:len(stk)-1] } if len(stk) > 0 { left[i] = stk[len(stk)-1] } else { left[i] = -1 } stk = append(stk, i) } for i, h := range heights { res = max(res, h*(right[i]-left[i]-1)) } return res } Swift class Solution { func maximalRectangle(_ matrix: [String]) -> Int { guard let firstRow = matrix.first else { return 0 } let n = firstRow.count var heights = [Int](repeating: 0, count: n) var ans = 0 for row in matrix { for (j, char) in row.enumerated() { if char == "1" { heights[j] += 1 } else { heights[j] = 0 } } ans = max(ans, largestRectangleArea(heights)) } return ans } private func largestRectangleArea(_ heights: [Int]) -> Int { var res = 0 let n = heights.count var stack = [Int]() var left = [Int](repeating: -1, count: n) var right = [Int](repeating: n, count: n) for i in 0..<n { while !stack.isEmpty && heights[stack.last!] >= heights[i] { right[stack.removeLast()] = i } left[i] = stack.isEmpty ? -1 : stack.last! stack.append(i) } for i in 0..<n { res = max(res, heights[i] * (right[i] - left[i] - 1)) } return res } } 方法二 C++ class Solution { public: int maximalRectangle(vector<string>& matrix) { if (matrix.empty()) return 0; int n = matrix[0].size(); vector<int> heights(n); int ans = 0; for (auto& row : matrix) { for (int j = 0; j < n; ++j) { if (row[j] == '1') ++heights[j]; else heights[j] = 0; } ans = max(ans, largestRectangleArea(heights)); } return ans; } int largestRectangleArea(vector<int>& heights) { int res = 0, n = heights.size(); stack<int> stk; vector<int> left(n, -1); vector<int> right(n, n); for (int i = 0; i < n; ++i) { while (!stk.empty() && heights[stk.top()] >= heights[i]) { right[stk.top()] = i; stk.pop(); } if (!stk.empty()) left[i] = stk.top(); stk.push(i); } for (int i = 0; i < n; ++i) res = max(res, heights[i] * (right[i] - left[i] - 1)); return res; } };