企业官网建设流程全解析

无锡哪里有做网站,烟台网站建设方案优化,野花视频直播免费观看7,沙洋网站开发【LetMeFly】2943.最大化网格图中正方形空洞的面积#xff1a;小小思维 力扣题目链接#xff1a;https://leetcode.cn/problems/maximize-area-of-square-hole-in-grid/ 给你一个网格图#xff0c;由 n 2 条 横线段 和 m 2 条 竖线段 组成#xff0c;一开始所有区域均为…【LetMeFly】2943.最大化网格图中正方形空洞的面积小小思维力扣题目链接https://leetcode.cn/problems/maximize-area-of-square-hole-in-grid/给你一个网格图由n 2条横线段和m 2条竖线段组成一开始所有区域均为1 x 1的单元格。所有线段的编号从1开始。给你两个整数n和m。同时给你两个整数数组hBars和vBars。hBars包含区间[2, n 1]内互不相同的横线段编号。vBars包含[2, m 1]内互不相同的竖线段编号。如果满足以下条件之一你可以移除两个数组中的部分线段如果移除的是横线段它必须是hBars中的值。如果移除的是竖线段它必须是vBars中的值。请你返回移除一些线段后可能不移除任何线段剩余网格图中最大正方形空洞的面积正方形空洞的意思是正方形内部不含有任何线段。示例 1输入n 2, m 1, hBars [2,3], vBars [2]输出4解释左边的图是一开始的网格图。 横线编号的范围是区间 [1,4] 竖线编号的范围是区间 [1,3] 。 可以移除的横线段为 [2,3] 竖线段为 [2] 。 一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。 操作后得到的网格图如右图所示。 正方形空洞面积为 4。 无法得到面积大于 4 的正方形空洞。 所以答案为 4 。示例 2输入n 1, m 1, hBars [2], vBars [2]输出4解释左边的图是一开始的网格图。 横线编号的范围是区间 [1,3] 竖线编号的范围是区间 [1,3] 。 可以移除的横线段为 [2] 竖线段为 [2] 。 一种得到最大正方形面积的方法是移除横线段 2 和竖线段 2 。 操作后得到的网格图如右图所示。 正方形空洞面积为 4。 无法得到面积大于 4 的正方形空洞。 所以答案为 4 。示例 3输入n 2, m 3, hBars [2,3], vBars [2,3,4]输出9解释左边的图是一开始的网格图。 横线编号的范围是区间 [1,4] 竖线编号的范围是区间 [1,5] 。 可以移除的横线段为 [2,3] 竖线段为 [2,3,4] 。 一种得到最大正方形面积的方法是移除横线段 2、3 和竖线段 3、4 。 操作后得到的网格图如右图所示。 正方形空洞面积为 9。 无法得到面积大于 9 的正方形空洞。 所以答案为 9 。提示1 n 1091 m 1091 hBars.length 1002 hBars[i] n 11 vBars.length 1002 vBars[i] m 1hBars中的值互不相同。vBars中的值互不相同。解题方法最大连续简单换个思维m i n ( 水平方向移除一些线后的最大连续空格 , 竖直方向移除一些线后的最大连续空格 ) min(水平方向移除一些线后的最大连续空格, 竖直方向移除一些线后的最大连续空格)min(水平方向移除一些线后的最大连续空格,竖直方向移除一些线后的最大连续空格)即为正方形的最大边长。水平方向移除一些线后的最大连续空格数是多少呢很简单把所有能移除的都移除呗。具体来说使用一个变量l a s t lastlast记录当前空格向右处理到哪条线了使用一个变量c n t cntcnt记录当前空格的连续长度。遍历分隔线数组如果当前能移除的分隔线正好等于l a s t 1 last1last1则空格可以继续网友拓展更新c n t 1 cnt1cnt1更新l a s t 1 last1last1否则说明上个连续空格无法拓展到这条线更新答案最大值并将c n t cntcnt初始化为2 22这条线可以移除空格长度为2更新last为当前这条线。时间复杂度O ( h log ⁡ h v log ⁡ v ) O(h\log hv\log v)O(hloghvlogv)其中h l e n ( h B a r s ) hlen(hBars)hlen(hBars)v l e n ( v B a r s ) vlen(vBars)vlen(vBars)空间复杂度O ( log ⁡ h log ⁡ v ) O(\log h\log v)O(loghlogv)时空复杂度的主要来源都是排序因为题目没说给定分隔线有序。AC代码C/* * LastEditTime: 2026-01-15 10:20:39 */classSolution{private:intgetMaxDiff(vectorintv){intlast1,cnt1,ans1;for(intt:v){if(tlast1){cnt;last;}else{ansmax(ans,cnt);cnt2;lastt;}}ansmax(ans,cnt);returnans;}public:intmaximizeSquareHoleArea(intn,intm,vectorinthBars,vectorintvBars){sort(hBars.begin(),hBars.end());sort(vBars.begin(),vBars.end());intsidemin(getMaxDiff(hBars),getMaxDiff(vBars));returnside*side;}inttestGetMaxDiff(vectorintv){returngetMaxDiff(v);}};同步发文于CSDN和我的个人博客原创不易转载经作者同意后请附上原文链接哦~千篇源码题解已开源