正文

[leetcode]85.maximalrectangle最大矩形(代码片段)

liuliu5151  liuliu5151  2022-12-15  734

关键词：

Given a 2D binary matrix filled with 0‘s and 1‘s, find the largest rectangle containing only 1‘s and return its area.

Example:

Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6

题意

给定一个01矩阵，找出其中全由1构成的最大矩形。

思路

将所有1连接的部分看成一个bar height，这个题就可以看成是[leetcode]84. Largest Rectangle in Histogram直方图中的最大矩形

的followup，进行代码复用

代码

 1 class Solution 
 2     public int maximalRectangle(char[][] matrix) 
 3        if(matrix.length==0 || matrix[0].length==0) return 0;
 4        int row = matrix.length;
 5         int col = matrix[0].length;
 6         int [] heights = new int[col];
 7         int area = 0;
 8         for(int i = 0; i< row; i++)
 9             for(int j = 0; j< col; j++)
10                 if(matrix[i][j]==‘1‘)
11                     heights[j]++;
12                 else
13                     heights[j]=0;
14                 
15                 
16                  
17            area = Math.max(area,  largestRectangle(heights));
18         
19          return area;     
20     
21     
22     public int largestRectangle(int[] heights )
23         int area = 0;
24         Stack<Integer> s = new Stack<>();
25         for(int i = 0; i<=heights.length;)
26             int value = i<heights.length ? heights[i] : 0;
27             if(s.isEmpty() || value > heights[s.peek()])
28                 s.push(i);
29                 i++;
30             else
31                 int temp = s.pop();
32                 area = Math.max(area, heights[temp]*(s.isEmpty()? i: i-s.peek()-1));
33             // end else 
34         // end for 
35         return area; 
36     
37

leetcode352&leetcode239&leetcode295&leetcode53&leetcode209(代码片段)

lc352DataStreamasDisjointIntervals可以用treemap解key保存interval的start，value保存interval的end。分别找出当前val的lowerKey（treemap中>val的最小key值，没有就返回null）和higherKey(<val的最大key没有就返回null)有以下几种情况：1）当前插入的key... 查看详情

leetcode分类刷题（续2）(代码片段)

leetcode分类刷题1.递归1.1leetcode509斐波拉契数列1.2leetcode206反转链表1.3leetcode344反转字符串2.分治法2.1归并排序2.2leetcode169多数元素2.3leetcode53最大子序和2.4leetcode215数组中k大元素3.回溯法3.1leetcode78子集（模板）3.2leetcode22括号... 查看详情

leetcode分类刷题(代码片段)

leetcode学习笔记Java版1.数组操作1.1leetcode27移除元素1.2leetcode283移动零1.3leetcode485最大连续1的个数2.链表操作2.1leetcode203移除链表元素2.2leetcode206反转链表3.Java队列Queue3.1leetcode933最近的请求次数（仅一道题目）3.2leetcode239滑动... 查看详情

leetcode每日leetcode一题(代码片段)

其实有些算法思路挺有意思的，决定开始刷刷leetcode，先从简单的题开始吧！非最优解，仅记录分享CSDN链接githubleetcode链接文章目录CSDN链接[githubleetcode链接](https://github.com/smileyqp/frontend_book/blob/master/leetcode.md)6.161、查看详情

leetcode每日leetcode一题(代码片段)

链表-leetcode2&leetcode23(代码片段)

链表-Leetcode2&Leetcode23githubrepo地址:https://github.com/GoldenaArcher/js_leetcode，Github的目录大概会更新的更勤快一些。2.AddTwoNumbers题目地址：2.AddTwoNumbersAddTwoNumbers题目如下：Youaregiventwonon-em 查看详情

链表-leetcode2&leetcode23(代码片段)

leetcode刷题系列之-多数之和类型

...组合问题衍生到背包问题多数之和1.两数之和-力扣（LeetCode）167.两数之和II-输入有序数组-力扣（LeetCode）15.三数之和-力扣（LeetCode）16.最接近的三数之和-力扣（LeetCode）18.四数之和-力扣（LeetCode... 查看详情