本文主要是介绍LeetCode 题解（100）: Maximal Rectangle，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目：
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing all ones and return its area.
题解：
在Largest Rectangle in Histogram 的神算法的基础上略作改变即可。
c++版：
class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {if(matrix.size() == 0)return 0;vector<int> height(matrix[0].size());int maxArea = 0;for(int i = 0; i < matrix.size(); i++) {for(int j = 0; j < matrix[0].size(); j++) {if(matrix[i][j] == '0')height[j] = 0;elseheight[j] = height[j] + 1;}int cur = maximalArea(height);if(cur > maxArea)maxArea = cur;}return maxArea;}int maximalArea(vector<int>& height) {height.push_back(0);stack<int> index;int maxArea = 0;int i = 0;while(i < height.size()) {if(index.size() == 0 || height[index.top()] <= height[i])index.push(i++);else {int t = index.top();index.pop();maxArea = max(maxArea, height[t] * (index.size() == 0 ? i : i - 1 - index.top()));}}return maxArea;}
};Java版：
public class Solution {public int maximalRectangle(char[][] matrix) {if(matrix.length == 0)return 0;int[] height = new int[matrix[0].length];int maxArea = 0;for(int i = 0; i < matrix.length; i++) {for(int j = 0; j < matrix[0].length; j++) {if(matrix[i][j] == '0')height[j] = 0;elseheight[j] += 1;}int cur = largestRectangleArea(height);if(cur > maxArea)maxArea = cur;}return maxArea;}public int largestRectangleArea(int[] height) { int[] h = new int[height.length + 1]; h = Arrays.copyOf(height, height.length + 1); Stack<Integer> index = new Stack<>(); int i = 0; int maxArea = 0; while(i < h.length) { if(index.isEmpty() || h[index.peek()] <= h[i]) { index.push(i++); } else { int t = index.pop(); maxArea = Math.max(maxArea, h[t] * (index.isEmpty() ? i : i - 1 - index.peek())); } } return maxArea; }
}Python版：
class Solution:# @param {character[][]} matrix# @return {integer}def maximalRectangle(self, matrix):if len(matrix) == 0:return 0height = [0] * len(matrix[0])maxArea = 0for i in range(len(matrix)):for j in range(len(matrix[0])):if matrix[i][j] == '0':height[j] = 0else:height[j] += 1cur = self.largestRectangleArea(height)if cur > maxArea:maxArea = curreturn maxAreadef largestRectangleArea(self, height): height.append(0) maxArea = 0 i = 0 index = [] while i < len(height): if len(index) == 0 or height[index[-1]] <= height[i]: index.append(i) i += 1 else: t = index.pop() if len(index) == 0: maxArea = max(maxArea, height[t] * i) else: maxArea = max(maxArea, height[t] * (i - 1 - index[-1])) return maxArea这篇关于LeetCode 题解（100）: Maximal Rectangle的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
