洞穴中的矿物——设计一个 O(mlogn) 时间复杂度算法
Mineral in a Cave-Devise a O(mlogn) time complexity algorithm
*问题：洞穴中的矿物
钟乳石或石笋的长度是该列中 1 的个数。鉴于这样的
如图所示，设计一个输出以下值的 O(m log n) 算法：
max(最长钟乳石长度,最长石笋长度).
[预期：您算法的伪代码以及您的算法的清晰英文描述
该算法在做什么以及为什么它是正确的。]*
我正在考虑伪代码，但为了遍历像素网格，我需要两个时间复杂度为 O(n*m) 的循环，但所需的是 O(mlogn)。知道如何制作更熟练的伪代码
对于每一列：
- 检查顶部+底部像素，看它是钟乳石、石笋、满的还是空的 - O(1)
- 如果是钟乳石或石笋，二分查找确定长度 - O(log n)
- 记住找到的最长长度 - O(1)
*问题：洞穴中的矿物
钟乳石或石笋的长度是该列中 1 的个数。鉴于这样的 如图所示，设计一个输出以下值的 O(m log n) 算法： max(最长钟乳石长度,最长石笋长度).
[预期：您算法的伪代码以及您的算法的清晰英文描述 该算法在做什么以及为什么它是正确的。]*
我正在考虑伪代码，但为了遍历像素网格，我需要两个时间复杂度为 O(n*m) 的循环，但所需的是 O(mlogn)。知道如何制作更熟练的伪代码
对于每一列：
- 检查顶部+底部像素，看它是钟乳石、石笋、满的还是空的 - O(1)
- 如果是钟乳石或石笋，二分查找确定长度 - O(log n)
- 记住找到的最长长度 - O(1)