LC每日一题
- 最大正方形 在一个由 0 和 1 组成的二维矩阵内，找到只包含 1 的最大正方形，并返回其面积。
思路
dp[i][j]表示以matrix[i][j]为右下角的正方形的最大边长
代码
class Solution {
public int maximalSquare(char[][] matrix) {
if(matrix==null||matrix.length==0||matrix[0].length==0)return 0;
int rows=matrix.length;
int cols=matrix[0].length;
int[][] dp=new int[rows][cols];
int max=0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(matrix[i][j]=='1'){
if(i==0||j==0)dp[i][j]=1;
else dp[i][j]=Math.min(dp[i][j-1],Math.min(dp[i-1][j],dp[i-1][j-1]))+1;
}
max=Math.max(max,dp[i][j]);
}
}
return max*max;
}
}
1277. 统计全为 1 的正方形子矩阵
给你一个 m * n 的矩阵，矩阵中的元素不是 0 就是 1，请你统计并返回其中完全由 1 组成的 正方形 子矩阵的个数。
思路
和上题一样，只不过只要最小边不是1的话，就根据边的大小来计算有多少种正方形
class Solution {
public int countSquares(int[][] matrix) {
if(matrix==null||matrix.length==0||matrix[0].length==0)return 0;
int rows=matrix.length;
int cols=matrix[0].length;
int[][] dp=new int[rows][cols];
int ans=0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(matrix[i][j]==1){
if(i==0||j==0){
dp[i][j]=1;
ans++;
}else{
dp[i][j]=Math.min(Math.min(dp[i][j-1],dp[i-1][j]),dp[i-1][j-1])+1;
if(dp[i][j]!=1){
ans+=dp[i][j];
}else ans++;
}
}
}
}
return ans;
}
}
85. 最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
思路
矩形不能像正方形那样通过左上左上角的值来求边长，所以就采用对每一列依次往上求面积，同时保存每行的最小值 dp[i][j]表示第i行第j列左边的最长边长多少。然后以j列为基础依次往上计算，取边长最小值*高。高是每次加1的，相当于i到i-1到i-2这样
代码
class Solution {
public int maximalRectangle(char[][] matrix) {
if(matrix.length==0)return 0;
int rows=matrix.length;
int cols=matrix[0].length;
int[][] dp=new int[rows][cols];
int max=0;
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
if(matrix[i][j]=='1'){
if(j==0)dp[i][j]=1;
else dp[i][j]=1+dp[i][j-1];
int width=dp[i][j];
for(int k=i;k>=0;k--){
width=Math.min(width,dp[k][j]);
max=Math.max(max,width*(i-k+1));
}
}
}
}
return max;
}
}
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。求在该柱状图中，能够勾勒出来的矩形的最大面积。有点类似接雨水
思路
1.暴力就是用一个min保存到当前为止的最小值，O(n^2)，然后求当前坐标前面的所有可能。 2.分治就是找到最小值求面积，然后对最小值左边的区域递归求面积，右边区域也递归求面积 3.最小值队列就是维护一个到i位置的最小值队列，每当到一个新的位置，如果小于队尾，就将队尾位置弹出，代表这个位置的高度已经可求了（同时要弹出栈里相同值的位置），然后就分情况，看栈空不空来决定左界，右界是index 4.可用哨兵来优化，最小队列，就是在原数组的头尾分别放入一个哨兵0，选0是因为要保证哨兵是最小值，这样队列就永远非空，不用做空判断，且尾哨兵会将队中剩余的递增元素从尾巴全部弹出，不需要两次迭代
分治
class Solution {
public int largestRectangleArea(int[] heights) {
if(heights==null||heights.length==0)return 0;
return max(0,heights.length-1,heights);
}
int max(int low,int high,int[] heights){
if(low>high)return 0;
int min=low;
for(int i=low;i<=high;i++)
if(heights[i]<heights[min])
min=i;
int max=heights[min]*(high-low+1);
int left=max(low,min-1,heights);
int right=max(min+1,high,heights);
return Math.max(Math.max(max,left),right);
}
}
最小值队列/单调栈
class Solution {
public int largestRectangleArea(int[] heights) {
if(heights==null||heights.length==0)return 0;
Deque<Integer> queue=new LinkedList<>();
int max=0;
int index=0;
while(index<heights.length){
while(!queue.isEmpty()&&heights[index]<heights[queue.peekLast()]){
int tmp=queue.pollLast(); //此处如果队列有和弹出相同值的位置不管，因为最终会被弹出，且结果才是正确的
if(!queue.isEmpty())
max=Math.max(max,(index-queue.peekLast()-1)*heights[tmp]);
else
max=Math.max(max,index*heights[tmp]);
}
queue.offer(index++);
}
while(!queue.isEmpty()){
int tmp=queue.pollLast();
if(queue.isEmpty())max=Math.max(max,heights[tmp]*heights.length);
else max=Math.max(max,heights[tmp]*(heights.length-queue.peekLast()-1));
}
return max;
}
}
最小值队列加上哨兵法，就是扩容两个位置，同尾放入的是可取的最小值
class Solution {
public int largestRectangleArea(int[] heights) {
if(heights==null||heights.length==0)return 0;
if(heights.length==1)return heights[0];
Deque<Integer> queue=new LinkedList<>();
int[] h=new int[heights.length+2];
h[0]=0;h[heights.length+1]=0;
System.arraycopy(heights,0,h,1,heights.length);
int max=0;
int index=1;
queue.offer(0);
while(index<h.length){
while(h[index]<h[queue.peekLast()])
max=Math.max(max,h[queue.pollLast()]*(index-queue.peekLast()-1));
queue.offer(index++);
}
return max;
}
}
560. 和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。该题数组可以取负值，且无序，所以不能单纯使用双指针加前缀和
思路
因为该题为无序数组，且存在负值，所以必须用前缀和+哈希。 单纯的双指针只能用在非负的无序数组，一旦存在负数就没办法靠移动头尾指针来加减和，因为本身双指针就是前缀和的思想。 所以此题用前缀和，每次遍历到一个新数就求和，然后看是否=k，等于k的话先+1，再去看是否之前的前缀和中存在0（通过map），因为sum[i]-sum[j]=k，0...j...i...nums.length-1
class Solution {
public int subarraySum(int[] nums, int k) {
if(nums==null||nums.length==0)return 0;
HashMap<Integer,Integer> map=new HashMap<>();
int sum=0,ans=0;
for(int i=0;i<nums.length;i++){
sum+=nums[i];
if(sum==k)ans++;
if(map.containsKey(sum-k)){
ans+=map.get(sum-k);
}
map.put(sum,map.getOrDefault(sum,0)+1);
}
return ans;
}
}