C++ 中查找给定数组中的所有好索引

概述

在问题解决和编程中，有效搜索数组属性以查找特定索引是一个反复出现的问题。在数组中查找“好”索引就是这样一个问题。“好”索引通常满足一组约束，例如在其周围特定长度的非递增或非递减子数组。在本文中，我们将介绍如何使用 C++ 在给定数组中查找所有“好”索引。

问题陈述

对于长度为 n 的数组 arr[] 和整数 k，如果以下条件成立，则索引 i 是“好”索引：

• 直到索引 i 的 k 个元素构成一个非递增子数组。
• 在索引 i 处或之后的 k 个元素是一个非递减子数组。
• 索引 i 必须有效，即它在两侧必须至少有 k 个元素。

问题是定位并返回数组中所有此类“好”索引。

方法：两遍遍历法

为了高效地解决此问题，我们使用两遍遍历法

1. 预计算非递增计数： 创建一个数组 left[]，其中 left[i] 存储 i 之前连续非递增元素的数量。
2. 预计算非递减计数： 创建一个数组 right[]，其中 right[i] 存储 i 之后连续非递减元素的数量。
3. 查找有效索引： 遍历数组并检查 left[i] >= k 和 right[i] >= k 是否都满足。如果两个条件都满足，则 i 是一个“好”索引。

这种方法确保我们只需要遍历数组几次，从而实现 O(n) 时间复杂度的有效解决方案。

示例

让我们举一个例子来查找给定 C++ 数组中的所有“好”索引。

输出

Good Indices: 2 3 7   

代码说明

1. 初始化
   • left[] 跟踪前面连续非递增元素的长度。
   • right[] 跟踪后面连续非递减元素的长度。
   • 结果跟踪“好”索引。
2. 填充 left[] 数组
   • 如果 nums[i] <= nums[i-1]，我们增加 left[i]。
3. 填充 right[] 数组
   • 如果 nums[i] <= nums[i+1]，我们增加 right[i]。
4. 有效索引检查
   • 如果 left[i-1] >= k-1 且 right[i+1] >= k-1，则索引 i 是一个“好”索引并添加到结果中。

复杂度分析

• 构建 left[] 和 right[]：O(n)
• 检查有效索引：O(n)
• 总复杂度：O(n)

它使得解决方案高效且适用于大型输入。

示例演练

考虑 nums = {2, 1, 1, 1, 3, 4, 1, 2, 5, 6}，k = 2

1. 计算 left[]
   left = {0, 1, 2, 3, 0, 0, 1, 0, 0, 0}
2. 计算 right[]
   right = {0, 0, 0, 0, 1, 2, 0, 1, 2, 3}
3. 查找“好”索引
   • 对于有效索引，检查 left[i-1] >= 1 且 right[i+1] >= 1。
   • 结果为：{3, 4, 5}。

考虑的边缘情况

1. 数组大小较小 (n < 2k)
   • 不存在有效索引，因此返回空列表。
2. 已排序的递增/递减数组
   • 中间元素可以是“好”索引。
3. 所有元素都相同
   • 每个索引（边界条件除外）都可以是“好”索引。
4. 没有有效索引
   • 如果没有索引满足条件，则返回空列表。

替代方法（滑动窗口）

我们可以不预先计算 left[] 和 right[]，而是实现一个滑动窗口来动态检查非递增和非递减属性。它仍然需要 O(n) 时间，但可能更难优雅地实现。

结论

总之，数组中的“好”索引是可以通过预计算数组有效解决的常见问题之一。以下 O(n) 解决方案提供了最佳性能，同时易于理解。它是前缀计算和动态条件在优化基于数组的算法中的一个很好的例子。

通过使用两遍遍历法，我们可以有效地找到数组中的“好”索引，这可以应用于解决竞争性编程和技术面试中的其他类似问题。