网站建设前的分析第一小节内容,wordpress自带主题下载失败,万能浏览器安卓版下载,响应式培训网站模板下载文章目录题目描述思路 代码二刷题目描述
其实是84. 柱状图中最大的矩形的兄弟题目#xff0c;理解成多个84题#xff0c;对结果取max即可。
思路 代码
一行抽象出一个【柱状图】#xff0c;分别套到84题的函数里即可时空复杂度#xff1a;O(n2n…
文章目录题目描述思路 代码二刷题目描述
其实是84. 柱状图中最大的矩形的兄弟题目理解成多个84题对结果取max即可。
思路 代码
一行抽象出一个【柱状图】分别套到84题的函数里即可时空复杂度O(n2n^2n2)、O(n)
class Solution {public int maximalRectangle(char[][] matrix) {if(matrix null || matrix.length 0) {return 0;}// 看成【对每层进行柱状图最大面积判断】即可相当于固定底int max 0;int[] heights new int[matrix[0].length];for(int i 0; i matrix.length; i) {for(int j 0; j matrix[0].length; j) {if(matrix[i][j] 1) {heights[j];}else {heights[j] 0;}}max Math.max(max, largestRectangleArea(heights));}return max;}// 84. 求柱状图最大矩阵面积public int largestRectangleArea(int[] heights) {int res 0;DequeInteger stack new ArrayDeque();int[] newHeights new int[heights.length 2];for(int i 1; i heights.length 1; i) {newHeights[i] heights[i - 1];}for(int i 0; i newHeights.length; i) {while(!stack.isEmpty() newHeights[stack.peek()] newHeights[i]) {int index stack.pop();int l stack.peek();int r i;res Math.max(res, (r - l - 1) * newHeights[index]);}stack.push(i);}return res;}
}二刷
思路还是记得的
class Solution {public int maximalRectangle(char[][] matrix) {if(matrix null || matrix.length 0) return 0;int[] heights new int[matrix[0].length];int res 0;// 逐行转换for(int i 0; i matrix.length; i) {// 当前行的逐列维护for(int j 0; j matrix[0].length; j) {if(matrix[i][j] 1) {heights[j];}else {heights[j] 0;}}res Math.max(res, largestRectangleArea(heights));}return res;}public int largestRectangleArea(int[] heights) {int[] newHeights new int[heights.length 2];for(int i 1; i heights.length; i) {newHeights[i] heights[i - 1];}DequeInteger stack new ArrayDeque();int max 0;for(int i 0; i newHeights.length; i) {while(!stack.isEmpty() newHeights[i] newHeights[stack.peek()]) {int now stack.poll();int left stack.peek(); int right i; max Math.max(max, (right - left - 1) * newHeights[now]);}stack.push(i);}return max;}
}
