简约的网站设计/灯塔网站seo
原题链接:1413. 矩形牛棚 - AcWing题库
作为一个资本家,农夫约翰希望通过购买更多的奶牛来扩大他的牛奶业务。
因此,他需要找地方建立一个新的牛棚。
约翰购买了一大块土地,这个土地可以看作是一个 R 行(编号 1∼R)C 列(编号 1∼C)的方格矩阵。
不幸的是,他发现其中的部分方格区域已经被破坏了,因此他无法在整个R×C 的土地上建立牛棚。
经调查,他发现共有 P 个方格内的土地遭到了破坏。
建立的牛棚必须是矩形的,并且内部不能包含被破坏的土地。
请你帮约翰计算,他能建造的最大的牛棚的面积是多少。
输入格式
第一行包含三个整数 R,C,P。
接下来 P 行,每行包含两个整数 r,c,表示第 r 行第 c 列的方格区域内土地是被破坏的。
输出格式
输出牛棚的最大可能面积。
数据范围
1≤R,C≤3000
0≤P≤30000
1≤r≤R
1≤c≤C
输入样例:
3 4 2
1 3
2 1
输出样例:
6
解题思路:
此题主要是应用单调栈算法,不回单调栈的先去学习单调栈,单调栈主要解决的就是寻找此位置右边/左边第一个比它大/小的数,这个题为什么能够用单调栈来实现,在一个n*m的矩阵中,有一些被破坏的地,建一个牛棚无非就是抛开被破坏的地(不能占用)寻找一个最大的矩形。我们可以确定一下他的下边界,只要下边界确定了,我们利用前缀和的思想递归求一下此位置向上延申地最大长度,这样的话,我们遍历一遍下边界,每一次遍历调用一下单调栈求解此时的最大面积,最后取一个最大的即可。
#include<iostream> #include<stack> using namespace std; const int N=3005; int n,m,p; int h[N][N],vis[N][N]; int stk[N], top; int l[N], r[N]; int maxx; int work(int h[]) {h[0] = h[m + 1] = -1;//为了防止遍历的最后跳不出来,多加一个-1保证栈中元素可以出栈top = 0;//初始0stk[ ++ top] = 0;for (int i = 1; i <= m; i ++ )//寻找左边界{while (h[stk[top]] >= h[i]) top -- ;//从栈中找左边第一个比它小的l[i] = stk[top];//记录下来stk[ ++ top] = i;//最后别忘了入栈}top = 0;stk[ ++ top] = m + 1;for (int i = m; i; i -- )//寻找右边界{while (h[stk[top]] >= h[i]) top -- ;//从栈中找右边第一个比它小的r[i] = stk[top];stk[ ++ top] = i;}int res = 0;for (int i = 1; i <= m; i ++ )//最后做一下面积计算即可res = max(res, h[i] * (r[i] - l[i] - 1));//要减一不然多算一个return res; } int main(){cin>>n>>m>>p;for(int i=0;i<p;i++){int x,y;cin>>x>>y;vis[x][y]=1;}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){if(!vis[i][j]){//没有被损坏h[i][j]=h[i-1][j]+1;}}}for(int i=1;i<=n;i++){//遍历下边界maxx=max(maxx,work1(h[i]));}cout<<maxx<<endl;return 0; }
优化版本:
单调栈还有一种优化版本,省略了LR数组,在遍历的时候直接计算出来出来面积,代码很简短也优化了空间复杂度。
int work1(int h[]) {int top = 0, res = 0;// 因为是在出栈时统计,为保证遍历结束时所有下标都会被统计,默认 m + 1 位置存储 0for (int i = 1; i <= m + 1; ++ i ) {while (top&& h[stk[top]] >= h[i]) {int l = stk[top-- ];int r=(top == 0 ? i - 1 : i - stk[top] - 1);res = max(res, h[l] * r);}stk[++top] = i;}return res;
}
写在最后:
单调栈问题比较难理解,网上有很多版本,大家选择一个适合自己的当板子记住就行了,在学习单调栈的时候有几篇博客写的是不错的:
[数据结构]---单调栈-CSDN博客
[数据结构]——单调栈-CSDN博客
另外y总的讲解此题也是不错的选择:AcWing 1413. 矩形牛棚(每日一题)_哔哩哔哩_bilibili
学习单调栈可以去洛谷做一下入门单调栈:【模板】单调栈 - 洛谷
文章尚有不足,请各位大佬指出,若有更好的解法及模板大家一起分享。
PS:图为y总B站视频提供——作者:yxc
相关文章:

AcWing 1413. 矩形牛棚(每日一题)
原题链接:1413. 矩形牛棚 - AcWing题库 作为一个资本家,农夫约翰希望通过购买更多的奶牛来扩大他的牛奶业务。 因此,他需要找地方建立一个新的牛棚。 约翰购买了一大块土地,这个土地可以看作是一个 R 行(编号 1∼R&…...

macOS Sonoma 14.4.1 (23E224) 正式版发布,ISO、IPSW、PKG 下载
macOS Sonoma 14.4.1 (23E224) 正式版发布,ISO、IPSW、PKG 下载 2024 年 3 月 26 日凌晨,macOS Sonoma 14.4.1 更新修复了一个可能导致连接到外部显示器的 USB 集线器无法被识别的问题。它还解决了可能导致 Java 应用程序意外退出的问题,并修…...

WPF使用外部字体,思源黑体,为例子
1.在工程中新建文件夹,命名为“Font"。 2.将下载好的字体文件复制到Font文件夹。 3.在工程中,加入静态资源 <Window.Resources><FontFamily x:Key"SYBold">/AnalyzeImage;Component/Font/#思源黑体 CN Bold</FontFamily…...

9、jenkins微服务持续集成(一)
文章目录 一、流程说明二、源码概述三、本地部署3.1 SpringCloud微服务部署本地运行微服务本地部署微服务3.2 静态Web前端部署四、Docker快速入门一、流程说明 Jenkins+Docker+SpringCloud持续集成流程说明 大致流程说明: 开发人员每天把代码提交到Gitlab代码仓库Jenkins从G…...

VOC(客户之声)赋能智能家居:打造个性化、交互式的未来生活体验
随着科技的飞速发展,智能家居已成为现代家庭不可或缺的一部分。然而,如何让智能家居更好地满足用户需求,提供更贴心、更智能的服务,一直是行业关注的焦点。在这个背景下,VOC(客户之声)作为一种用…...

时序预测 | Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测
时序预测 | Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测 目录 时序预测 | Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测预测效果基本介绍程序设计参考资料 预测效果 基本介绍 1.Matlab实现GWO-BP灰狼算法优化BP神经网络时间序列预测(完整源码和数据…...

node.js学习(2)
版权声明 以下文章为尚硅谷PDF资料,B站视频链接:【尚硅谷Node.js零基础视频教程,nodejs新手到高手】仅供个人学习交流使用。如涉及侵权问题,请立即与本人联系,本人将积极配合删除相关内容。感谢理解和支持,…...

【pytest】测试数据存储在 Excel 或 TXT 文件中,如何参数化
如果测试数据存储在 Excel 或 TXT 文件中,你可以使用外部库来读取这些数据,并将其转化为参数化测试所需的格式。下面我将分别展示如何从这两种文件中读取数据,并用于参数化测试。 从 Excel 文件中读取测试数据 你可以使用 pandas 库来读取 …...

ubuntu22.04@Jetson Orin Nano安装配置VNC服务端
ubuntu22.04Jetson Orin Nano安装&配置VNC服务端 1. 源由2. 环境3. VNC安装Step 1: update and install xserver-xorg-video-dummyStep 2: Create config for dummy virtual displayStep3: Add the following contents in xorg.conf.dummyStep 4: Update /etc/X11/xorg.con…...

面向对象特征二:继承
继承的概述 生活中的继承 财产继承: 绿化:前人栽树,后人乘凉 “绿水青山,就是金山银山” 样貌: 继承之外,是不是还可以"进化": 继承有延续(下一代延续上一代的基因、财…...

宝塔面板CentOS Stream 8 x86 下如何安装openlitespeed
宝塔自带的软件商店里如果没办法安装,那么我们可以通过指令来手动安装: 第一步: yum install epel-release Package epel-release-8-19.el8.noarch is already installed. Dependencies resolved. Nothing to do. Complete! 第二步&#…...

LeetCode 2952.需要添加的硬币的最小数量:贪心(排序)
【LetMeFly】2952.需要添加的硬币的最小数量:贪心(排序) 力扣题目链接:https://leetcode.cn/problems/minimum-number-of-coins-to-be-added/ 给你一个下标从 0 开始的整数数组 coins,表示可用的硬币的面值ÿ…...

基于SpringBoot + Vue实现的在线装修管理系统设计与实现+毕业论文
介绍 系统包含用户、装修队、管理员三个角色 管理员: 管理员管理:管理其他管理员的账号和权限,确保系统管理的层次化和安全性。 装修队管理:审核装修队的资质,管理装修队的人员信息,监控工程进度ÿ…...

阿里云安全产品简介,Web应用防火墙与云防火墙产品各自作用介绍
在阿里云的安全类云产品中,Web应用防火墙与云防火墙是用户比较关注的安全类云产品,二则在作用上并不是完全一样的,Web应用防火墙是一款网站Web应用安全的防护产品,云防火墙是一款公共云环境下的SaaS化防火墙,本文为大家…...

作业 二维数组-定位问题
图形相似度 描述 给出两幅相同大小的黑白图像(用0-1矩阵)表示,求它们的相似度。 说明:若两幅图像在相同位置上的像素点颜色相同,则称它们在该位置具有相同的像素点。 两幅图像的相似度定义为相同像素点数占总像素点数…...

通过Jmeter准备压测数据-mysql示例
1、新建线程组 总共30万条数据 2、创建jdbc链接 创建jdbc连接配置 配置mysql连接 需要在jmeter安装的路径\apache-jmeter-5.6.3\lib\ext 目录下添加mysql 驱动 3、创建jdbc请求 jdbc链接名称需要与上一步中的保持一致,同时添加insert语句 例如 INSERT INTO test…...

如何系统的自学python?
系统地自学Python是一个循序渐进的过程,以下是一份详细的指南,帮助你从零开始逐步掌握这门语言: 1、了解Python及其应用场景: 阅读关于Python的简介,理解它为何流行,以及在哪些领域(如Web开发…...

记录一个写自定义Flume拦截器遇到的错误
先说结论: 【结论1】配置文件中包名要写正确 vim flume1.conf ... a1.sources.r1.interceptors.i1.type com.atguigu.flume.interceptor.MyInterceptor2$MyBuilder ... 标红的是包名,表黄的是类名,标蓝的是自己加的内部类名。这三个都…...

Codeforces Round 934 (Div. 2) D. Non-Palindromic Substring
题目 思路: #include <bits/stdc.h> using namespace std; #define int long long #define pb push_back #define fi first #define se second #define lson p << 1 #define rson p << 1 | 1 const int maxn 1e6 5, inf 1e9, maxm 4e4 5; co…...

如何避免公网IP安全风险
目录 1. 使用防火墙 2. 定期更新和打补丁 3. 使用入侵检测和预防系统 4. 进行安全审计和监控 5. 实施最小权限原则 6. 使用VPN 7. 配置SSL/TLS 8. 使用DDoS保护服务 9. 强化认证措施 10. 定期备份数据 1. 使用防火墙 配置好网络防火墙,以允许仅必要的端口…...

探究 HTTPS 的工作过程
目录 1. HTTPS 协议原理 1.1. 为什么要有HTTPS协议 1.2. 如何理解安全 1.3. HTTPS 协议是什么 2. HTTPS 的前置概念 2.1. 什么是加密 && 解密 2.2. 为什么要加密 2.3. 常见的加密方式 2.3.1. 对称加密 2.3.2. 非对称加密 2.4. 数据摘要 && 数据指纹…...

算法学习——LeetCode力扣图论篇1
算法学习——LeetCode力扣图论篇1 797. 所有可能的路径 797. 所有可能的路径 - 力扣(LeetCode) 描述 给你一个有 n 个节点的 有向无环图(DAG),请你找出所有从节点 0 到节点 n-1 的路径并输出(不要求按特…...

Stable Diffusion 模型下载:epiCPhotoGasm(真实、照片)
本文收录于《AI绘画从入门到精通》专栏,专栏总目录:点这里,订阅后可阅读专栏内所有文章。 文章目录 模型介绍生成案例案例一案例二案例三案例四案例五案例六案例七案例八 下载地址 模型介绍 该模型对照片是什么有很高的了解,所以…...

WPF 路由事件 数据驱动 、Window 事件驱动
消息层层传递,遇到安装有事件侦听器的对象,通过事件处理器响应事件,并决定事件是否继续传递; 后置代码中使用AddHandler方法设置事件监听器,该方法的 第一个参数是指定监听的路由事件类型对象, 第二个参数…...

【UI框架】——保姆式使用教程
👨💻个人主页:开发者-曼亿点 👨💻 hallo 欢迎 点赞👍 收藏⭐ 留言📝 加关注✅! 👨💻 本文由 曼亿点 原创 👨💻 收录于专栏:…...

第10讲:操作符详解
第10讲:操作符详解 1. 操作符的分类2. 二进制和进制转换2.1 二进制转十进制10进制转2进制数 2.2 二进制转八进制和十六进制2.2.1 二进制转八进制2.2.2 二进制转十六…...

数据可视化Grafana Windows 安装使用教程(中文版)
1.跳转连接 天梦星服务平台 (tmxkj.top)https://tmxkj.top/#/site?url 2.下载应用程序 官网地址:Grafana get started | Cloud, Self-managed, Enterprisehttps://grafana.com/get/ 3.修改配置文件 grafana\conf\defaults 4.启动\bin\目录下serve应用程序 浏…...

【No.21】蓝桥杯组合数学|数位排序|加法计数原理|乘法计数原理|排列数|组合数|抽屉原理|小蓝吃糖果|二项式定理|杨辉三角|归并排序(C++)
组合数学 数位排序 【问题描述】 小蓝对一个数的数位之和很感兴趣,今天他要按照数位之和给数排序。当两个数各个数位之和不同时,将数位和较小的排在前面,当数位之和相等时,将数值小的排在前面。 例如,2022 排在 409 前面, 因为 2022 的数位之和是 6,小于 409 的数位 之和 13。…...

主流公链 - Monero
Monero: 加密货币的隐私标杆 1. 简介 Monero(XMR),世界语中货币的意思,是一种去中心化的加密货币,旨在提供隐私和匿名性。与比特币等公开区块链不同,Monero专注于隐私保护,使用户的交易记录和余…...

C#中让字典、列表、数组作为只读的方法参考
一、字典 在 C# 中,可以通过使用 ReadOnlyDictionary<TKey, TValue> 类或者是通过调用普通字典的 .AsReadOnly() 方法来创建一个只读的字典。ReadOnlyDictionary 不允许修改字典,任何试图改变字典的操作都会抛出 NotSupportedException。 以下是使…...