本文主要是介绍LeetCode 85 Maximal Rectangle (最大子矩形 单调栈)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
Given a 2D binary matrix filled with 0's and 1's, find the largest rectangle containing only 1's and return its area.
For example, given the following matrix:
1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0
Return 6.
题目链接：https://leetcode.com/problems/maximal-rectangle/
题目分析：和正方形不同，不能记录边长做，将问题转化成n个一维的最大子矩形，经典的单调栈算法搞一搞，复杂度O(mn)
public class Solution {public int maximalRectangle(char[][] matrix) {int n = matrix.length;if (n == 0) {return 0;}int m = matrix[0].length;int[] heights = new int[m + 1];Stack<Integer> stk = new Stack<>();int ans = 0, cur, w, pos;for (int i = 0; i < n; i ++) {for (int j = 0; j < m; j ++) {if (matrix[i][j] == '1') {heights[j] += 1;}else {heights[j] = 0;}}pos = 0;while(!stk.empty()) {stk.pop();}while (pos <= m) {if (stk.empty() || heights[stk.peek()] <= heights[pos]) {stk.push(pos ++);}else {cur = stk.peek();stk.pop();w = stk.empty() ? pos : pos - stk.peek() - 1;ans = Math.max(ans, w * heights[cur]);}}}return ans;}
}
这篇关于LeetCode 85 Maximal Rectangle (最大子矩形 单调栈)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
