当前位置: 首页 > news >正文

【LeetCode】85. 最大矩形 (暴力枚举)

85. 最大矩形 - 力扣(LeetCode)

题目:

思路:

单调栈的运用

相似题:1504. 统计全 1 子矩形 - 力扣(LeetCode)

解法有两种,一种是暴力枚举,一种是单调栈优化

暴力做法很简单,我们同样枚举上界下界,然后枚举列数即可,同时这里我们可以使用一个简单的思路来计算连读h段的长度,可以先去写一下连续0段这题

代码很简单,但是时间复杂度很大,所以不妨考虑优化

我们发现我们题目其实可以变成一个柱形图,什么意思呢?

假设我们枚举到了第 i 行,那么对于每一个 sum[i][j],我们定义为 i 位置往上的最长连读 1 的数量,那么这样一转换就变成了一个柱形图,如

那么这样一直枚举行就相当于每次都求一个矩形图的最大矩形,这样以来我们就优化成了 O(N*M) 的复杂度,大大加快了速率

具体的,我们提前预处理出 sum[i][j],然后暴力枚举 i,对每个 i 都做一个单调栈的操作,同时不要忘了哨兵

参考视频:LeetCode-85 最大矩形 最近太忙啦!水一个视频~_哔哩哔哩_bilibili

代码:

class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();int ans = 0;for(int i = 0;i < n;i++){vector<int> sum(m,0);for(int j = i;j < n;j++){int last = -1;int h = j - i + 1;for(int z =0;z < m;z++){sum[z] += matrix[j][z] - '0';if(sum[z] == h) ans = max(ans,h * (z - last));else last = z;}}}return ans;}
};
class Solution {
public:int maximalRectangle(vector<vector<char>>& matrix) {int n = matrix.size();int m = matrix[0].size();vector<vector<int>> sum(n,vector<int>(m+2,0));for(int i = 0;i < n;i++){for(int j = 0;j < m;j++){if(matrix[i][j] == '0') continue;if(i) sum[i][j+1] = sum[i-1][j+1];sum[i][j+1]++;}}int ans = 0;for(int i = 0;i < n;i++){stack<int> st;for(int j = 0;j < sum[i].size();j++){while(!st.empty() && sum[i][st.top()] > sum[i][j]){int h = sum[i][st.top()];st.pop();int w = j - st.top() - 1;ans = max(ans,h*w);}st.push(j);}}return ans;}
};

http://www.xdnf.cn/news/1352881.html

相关文章:

  • 嵌入式软件/硬件工程师面试题集
  • MySql知识梳理之DDL语句
  • 力扣hot100:搜索二维矩阵与在排序数组中查找元素的第一个和最后一个位置(74,34)
  • 知识蒸馏 Knowledge Distillation 概率链式法则(Probability Chain Rule)
  • Java接口响应速度优化
  • springboot项目结构
  • leetcode80:删除有序数组中的重复项 II(快慢指针法)
  • 日语学习-日语知识点小记-进阶-JLPT-N1阶段蓝宝书,共120语法(6):51-60语法
  • Day33 MLP神经网络的训练
  • 「ECG信号处理——(24)基于ECG和EEG信号的多模态融合疲劳分析」2025年8月23日
  • 前端 H5分片上传 vue实现大文件
  • 【卫星通信】超低码率语音编码ULBC:EnCodec神经音频编解码器架构深度解析
  • piclist+gitee操作指南
  • 【Day 11】238.除自身以外数组的乘积
  • Transformer核心概念I-token
  • SpringBoot 快速上手:从环境搭建到 HelloWorld 实战
  • Excel 条件高亮工具,秒高亮显示符合筛选条件的行数据
  • 「数据获取」《中国能源统计年鉴》(1986-2023)(获取方式看绑定的资源)
  • 蓝桥杯算法之基础知识(2)——Python赛道
  • 【51单片机学习】直流电机驱动(PWM)、AD/DA、红外遥控(外部中断)
  • mmdetection:记录算法训练配置文件
  • A Large Scale Synthetic Graph Dataset Generation Framework的学习笔记
  • Mysql EXPLAIN详解:从底层原理到性能优化实战
  • 如何在Ubuntu中删除或修改已有的IP地址设置?
  • C语言---数据类型
  • PyTorch生成式人工智能——VQ-VAE详解与实现
  • TypeScript 的泛型(Generics)作用理解
  • Kafka 概念与概述
  • 在TencentOS3上部署OpenTenBase:从入门到实战的完整指南
  • 【Java学习笔记】18.反射与注解的应用