科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载本篇技术指南以 codeforces-go 仓库中 leetcode/biweekly/118/b/README.md 的官方题解为主体结合仓库内 Go 源码与测试数据完整讲解 LeetCode 第 118 场双周赛 B 题函数签名maximizeSquareHoleArea的两种解法排序 线性扫描以及借用「128. 最长连续序列」哈希表技巧的线性时间解法。读完本文你将掌握这类删除障碍物求最大连通区域问题的贪心建模方式并能直接复用仓库中现成的 Go 实现与自动测试框架进行验证。题目背景一道阅读理解题该题出现在 LeetCode 第 118 场双周赛的 B 题位置仓库中对应目录为 leetcode/biweekly/118/b。题目给出一个网格横向hBars与纵向vBars各有一些可移除的栅栏线段要求计算移除若干线段后能够围出的最大正方形洞的面积。原题解作者在 README.md 开头就点明本题难度主要在读题。只要把题意抽象清楚算法本身非常简单。一个值得注意的细节是仓库中的 Go 实现把网格的行数n与列数m直接命名为_忽略见 b.go说明答案只由hBars和vBars两个数组决定n、m只用于界定栅栏编号的合法范围不影响最终计算。核心思路贪心 撤销删除题解的贪心推理分三步删除的线段越多洞的面积越大。因此先把所有能删的线段都删掉即把hBars、vBars中的全部线段移除此时会得到一个最大的矩形洞它的长与宽分别由横向、纵向的连续可删线段决定。求最大矩形分别算出横向、纵向的最长连续可删线段能撑开多大跨度两者相乘就是最大矩形面积。正方形约束题目要求正方形因此取长、宽的最小值作为正方形边长多删的那部分线段撤销删除即可——因为连续线段段可以整体保留一部分、丢弃一部分不会破坏剩下的连续段所以撤销在数学上总是可行的。为什么必须是连续的线段因为只要中间某一段没被删掉它就像一堵墙把洞隔成两半无法形成更大的完整孔洞。这是全题的唯一关键约束。从 hBars 推导规律以hBars为例题解给出了删除数量与可撑开长度的对应关系删除情况最长长度不删1删除一条线段2删除两条编号相邻的线段3删除三条编号连续的线段例如 2,3,44……依此类推……所以本题要做的事情被提炼为一句话把数组排序后求「最长连续递增子数组的长度」再加一就是该方向能撑开的跨度。最终正方形边长 min(横向跨度, 纵向跨度)面积 边长的平方。解法一排序 单次线性扫描O(n log n)这是 README 中的优化前版本先排序再线性扫描一遍数组统计连续递增的最长段长度。因为数组升序后a[i] a[i-1] 1就意味着这两根线段编号相邻属于同一段可删的连续线段。class Solution: # 返回 a 排序后的最长连续递增子数组的长度 def f(self, a: List[int]) - int: a.sort() mx cnt 0 for i, x in enumerate(a): if i 0 and x a[i - 1] 1: cnt 1 else: cnt 1 # 重新计数 mx max(mx, cnt) return mx def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) - int: side min(self.f(hBars), self.f(vBars)) 1 return side * sideclass Solution { public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) { int side Math.min(f(hBars), f(vBars)) 1; return side * side; } // 返回 a 排序后的最长连续递增子数组的长度 private int f(int[] a) { Arrays.sort(a); int mx 1; int cnt 1; for (int i 1; i a.length; i) { if (a[i] a[i - 1] 1) { cnt; mx Math.max(mx, cnt); } else { cnt 1; // 重新计数 } } return mx; } }class Solution { // 返回 a 排序后的最长连续递增子数组的长度 int f(vectorint a) { ranges::sort(a); int mx 1, cnt 1; for (int i 1; i a.size(); i) { if (a[i] a[i - 1] 1) { cnt; mx max(mx, cnt); } else { cnt 1; // 重新计数 } } return mx; } public: int maximizeSquareHoleArea(int, int, vectorint hBars, vectorint vBars) { int side min(f(hBars), f(vBars)) 1; return side * side; } };// 返回 a 排序后的最长连续递增子数组的长度 func f(a []int) (mx int) { slices.Sort(a) cnt : 0 for i, x : range a { if i 0 x a[i-1]1 { cnt } else { cnt 1 // 重新计数 } mx max(mx, cnt) } return mx } func maximizeSquareHoleArea(_, _ int, hBars, vBars []int) int { side : min(f(hBars), f(vBars)) 1 return side * side }其中f返回的是最长连续递增子数组的长度即连续可删线段的条数因此主函数要在此基础上1得到真正的边长最后side * side即为面积。复杂度分析解法一时间复杂度O(h·log h v·log v)其中h为hBars的长度v为vBars的长度瓶颈是两次排序。空间复杂度O(1)忽略排序的栈开销。解法二哈希集合优化到 O(n)借用 128. 最长连续序列 技巧排序是本题唯一的超线性开销。题解指出可以复用经典题128. 最长连续序列的哈希表技巧longestConsecutive把找最长连续段的过程降到线性先把所有数放进哈希集合去重然后只从序列起点即x-1不在集合中的x开始向后延伸每个元素至多被访问一次。class Solution: # 128. 最长连续序列 def longestConsecutive(self, nums: List[int]) - int: st set(nums) # 把 nums 转成哈希集合 ans 0 for x in st: # 遍历哈希集合 if x - 1 in st: # 如果 x 不是序列的起点直接跳过 continue # x 是序列的起点 y x 1 while y in st: # 不断查找下一个数是否在哈希集合中 y 1 # 循环结束后y-1 是最后一个在哈希集合中的数 ans max(ans, y - x) # 从 x 到 y-1 一共 y-x 个数 return ans def maximizeSquareHoleArea(self, n: int, m: int, hBars: List[int], vBars: List[int]) - int: side min(self.longestConsecutive(hBars), self.longestConsecutive(vBars)) 1 return side * sideclass Solution { public int maximizeSquareHoleArea(int n, int m, int[] hBars, int[] vBars) { int side Math.min(longestConsecutive(hBars), longestConsecutive(vBars)) 1; return side * side; } // 128. 最长连续序列 private int longestConsecutive(int[] nums) { SetInteger st new HashSet(); for (int num : nums) { st.add(num); // 把 nums 转成哈希集合 } int ans 0; for (int x : st) { // 遍历哈希集合 if (st.contains(x - 1)) { // 如果 x 不是序列的起点直接跳过 continue; } // x 是序列的起点 int y x 1; while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中 y; } // 循环结束后y-1 是最后一个在哈希集合中的数 ans Math.max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数 } return ans; } }class Solution { // 128. 最长连续序列 int longestConsecutive(vectorint nums) { unordered_setint st(nums.begin(), nums.end()); // 把 nums 转成哈希集合 int ans 0; for (int x : st) { // 遍历哈希集合 if (st.contains(x - 1)) { // 如果 x 不是序列的起点直接跳过 continue; } // x 是序列的起点 int y x 1; while (st.contains(y)) { // 不断查找下一个数是否在哈希集合中 y; } // 循环结束后y-1 是最后一个在哈希集合中的数 ans max(ans, y - x); // 从 x 到 y-1 一共 y-x 个数 } return ans; } public: int maximizeSquareHoleArea(int, int, vectorint hBars, vectorint vBars) { int side min(longestConsecutive(hBars), longestConsecutive(vBars)) 1; return side * side; } };// 128. 最长连续序列 func longestConsecutive(nums []int) (ans int) { has : map[int]bool{} for _, num : range nums { has[num] true // 把 nums 转成哈希集合 } for x : range has { // 遍历哈希集合 if has[x-1] { // 如果 x 不是序列的起点直接跳过 continue } // x 是序列的起点 y : x 1 for has[y] { // 不断查找下一个数是否在哈希集合中 y } // 循环结束后y-1 是最后一个在哈希集合中的数 ans max(ans, y-x) // 从 x 到 y-1 一共 y-x 个数 } return } func maximizeSquareHoleArea(_, _ int, hBars, vBars []int) int { side : min(longestConsecutive(hBars), longestConsecutive(vBars)) 1 return side * side }这段 Go 实现与仓库 b.go 完全一致用map[int]bool建哈希集合if has[x-1]判断x是否为序列起点for has[y]从起点向后延伸。longestConsecutive返回最长连续序列长度后同样1得到边长。复杂度分析解法二时间复杂度O(h v)其中h为hBars的长度v为vBars的长度。每个元素只入集一次且只会在所属连续段被扫描一次。空间复杂度O(h v)用于哈希集合。仓库源码与测试验证Go 实现文件仓库 leetcode/biweekly/118/b/b.go 完整给出了解法二。值得注意的两点函数签名maximizeSquareHoleArea(_, _ int, hBars, vBars []int) int中n、m被命名为_再次印证答案与网格行列数无关只与两个可删数组相关的读题结论题解按 128. 最长连续序列 的模板实现longestConsecutive作为通用工具函数可复用到同类题目。自动测试用例测试文件 b_test.go 由 copypasta/template/leetcode/generator_test.go 自动生成通过testutil.RunLeetCodeFuncWithFile(t, maximizeSquareHoleArea, b.txt, targetCaseNum)从 b.txt 读取样例数据。从 leetcode/testutil/leetcode.go 中RunLeetCodeFuncWithFile的实现看它按输入参数个数 输出个数本例为 4 1 5 行把文本文件切分成一组组样例再逐组断言运行结果targetCaseNum为 0 表示运行全部样例为 -1 表示只跑最后一个为正数表示先跑指定用例、通过后再跑全部用例见 leetcode.go 的逻辑。b.txt中共有 3 组样例每组 5 行n、m、hBars、vBars与期望输出nmhBarsvBars期望输出推导21[2,3][2]4f(h)2f(v)1side2面积 411[2][2]4f(h)1f(v)1side2面积 423[2,3][2,3,4]9f(h)2f(v)3side3面积 9在仓库leetcode/biweekly/118/b目录下执行go test即可运行这三组样例验证实现b.go位于package main与测试文件同包测试框架会自动解析参数并比较输出。相似题目与归类题解在 README 末尾列出了两道高度相关的题目可用于巩固删除障碍物 最长连续段/相邻区间这一套路1465. 切割后面积最大的蛋糕同样是从横纵两个方向考虑切割位置求最大矩形面积只是本题多了一步正方形的约束。2975. 移除栅栏得到的正方形田地的最大面积与本题几乎同构都是移除若干栅栏后求最大正方形。从分类看本题属于「贪心与思维」题单中的区间/思维/脑筋急转弯类别算法本身是朴素的线性扫描真正的门槛在于把题意抽象成最长连续递增子数组。小结「最大化网格正方形洞的面积」是一道典型的读懂题意即秒杀的题目贪心删除越多越好先全部删除得到最大矩形转化连续删除k条编号相邻的线段可撑开长度k1因此问题变成排序后最长连续递增子数组长度 1正方形边长取横向、纵向跨度的最小值面积即其平方复杂度排序版O(n log n)借用 128. 最长连续序列 的哈希表技巧可优化到O(n)。仓库 b.go 给出了与官方题解完全一致的 Go 实现b_test.go 与 b.txt 则提供了可直接运行的自动验证样例适合作为该套路题目的标准模板反复练习。赞分享科学计算【免费下载链接】codeforces-go算法竞赛模板库 by 灵茶山艾府 项目地址https://gitcode.com/GitHub_Trending/co/codeforces-go点击查看免费下载相关推荐Sails 框架下通过自定义 HTTP 中间件配置 P3P 隐私策略头P3P 兼容旧版 IE 应用实战指南Sails 框架下通过自定义 HTTP 中间件配置 P3P 隐私策略头P3P 兼容旧版 IE 应用实战指南 导读 本文讲解如何在 SailsNode.js科学计算codeforces-go 题解精读最小化字符串价值双周赛 126 第三题的堆与贪心两解法codeforces go 题解精读最小化字符串价值双周赛 126 第三题的堆与贪心两解法 导读 本文深入解析 LeetCode 第 126 场双周赛第三科学计算wvp-GB28181-pro一条命令拉起 GB28181 视频平台接入多品牌摄像头附避坑清单wvp GB28181 pro一条命令拉起 GB28181 视频平台接入多品牌摄像头附避坑清单 wvp GB28181 pro 是一个基于 GB/T 281后端音视频前端上一篇allReady数据模型详解活动、任务与资源的关系设计原理下一篇如何快速上手MelonLoaderUnity游戏模组加载的终极指南 创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考