该提问与当前博客内容无直接关联。 我将基于您提供的“流量波峰”问题背景，使用Python语言为您提供一个完整的解题方案。这个问题是一个典型的数组遍历与条件判断问题，核心在于高效地找到满足特定条件的三元组并计算其最小跨度。 ### 问题分析与算法设计 题目要求：给定一个整数数组 `nums`，找出所有满足条件的三元组 `(i, j, k)`，其中 `i < j < k`，且 `nums[j] > nums[i]` 且 `nums[j] > nums[k]`（即 `j` 是波峰）。最终需要返回所有满足条件的三元组中 `(k - i)` 的最小值。若不存在，返回 `-1`。 **核心挑战**：直接使用三重循环（时间复杂度 O(n³)）在 `n` 最大为 100000 的情况下是完全不可行的。我们需要设计更高效的算法。 **优化思路**： 1. **固定中间点 j**：对于数组中的每一个位置 `j` (1 ≤ j ≤ n-2)，我们可以将其视为候选的“波峰”。 2. **寻找左侧最小值**：为了满足 `nums[j] > nums[i]` 且 `i < j`，我们希望 `i` 尽可能小（以减小 `k-i` 的跨度），同时 `nums[i]` 也尽可能小（以更容易满足 `nums[j] > nums[i]` 的条件）。因此，对于每个 `j`，我们只需知道在它**左侧**（`[0, j-1]`）的最小值 `left_min` 及其索引 `left_min_idx`。如果 `nums[j] > left_min`，则 `(left_min_idx, j)` 可以构成一个候选的左侧对。 3. **寻找右侧满足条件的 k**：对于固定的 `j` 和左侧对 `(left_min_idx, j)`，我们需要在 `j` 的右侧找到一个 `k`，使得 `nums[j] > nums[k]`。同样，为了最小化 `k - left_min_idx`，我们应在右侧**从近到远**寻找第一个满足 `nums[k] < nums[j]` 的位置。然而，对于每个 `j` 都向后线性搜索 `k` 仍然是 O(n²) 的复杂度。 4. **进一步优化**：一个更优的策略是，对于每个 `j`，我们预先处理出其右侧第一个比它小的元素的索引。这可以通过**单调栈**技术在线性时间内完成。 ### 最终算法步骤 1. **预处理左侧最小索引**： * 创建一个数组 `left_min_idx`，其中 `left_min_idx[j]` 表示在位置 `j` 左侧（包括自身）的最小值元素的索引。这可以通过一次正向遍历完成。 2. **预处理右侧第一个较小值的索引**： * 创建一个数组 `right_smaller_idx`，其中 `right_smaller_idx[j]` 表示在位置 `j` 右侧第一个满足 `nums[k] < nums[j]` 的索引 `k`。这可以通过一次反向遍历结合单调递增栈完成。 3. **遍历与结果计算**： * 遍历每一个可能作为波峰的位置 `j` (从 1 到 n-2)。 * 获取其左侧最小值的索引 `i = left_min_idx[j-1]`。检查是否满足 `nums[j] > nums[i]`。 * 获取其右侧第一个较小值的索引 `k = right_smaller_idx[j]`。检查 `k` 是否有效（不为 -1 或超出范围）。 * 如果 `i` 和 `k` 都有效，则计算跨度 `span = k - i`，并更新全局最小跨度 `min_span`。 4. **返回结果**：如果 `min_span` 未被更新，则返回 `-1`，否则返回 `min_span`。 该算法的时间复杂度为 O(n)，空间复杂度为 O(n)，能够高效处理 n ≤ 100000 的数据规模。 ### Python 代码实现 ```python def find_min_span(nums): """ 找到满足波峰条件的三元组 (i, j, k) 的最小 (k-i) 值。 """ n = len(nums) if n < 3: return -1 # 1. 预处理左侧最小值的索引 left_min_idx = [0] * n left_min_idx[0] = 0 # 第一个元素的左侧最小索引就是它自己 for i in range(1, n): # 比较当前元素和之前记录的最小值，记录更小值的索引 if nums[i] < nums[left_min_idx[i-1]]: left_min_idx[i] = i else: left_min_idx[i] = left_min_idx[i-1] # 2. 预处理右侧第一个较小值的索引 (使用单调栈) right_smaller_idx = [-1] * n stack = [] # 单调递增栈，存储索引 for i in range(n-1, -1, -1): # 从右向左遍历 # 弹出栈顶所有值大于等于当前值的索引，因为它们不可能是当前值右侧的“第一个更小值” while stack and nums[stack[-1]] >= nums[i]: stack.pop() # 如果栈非空，栈顶索引对应的值就是当前值右侧第一个比它小的值 if stack: right_smaller_idx[i] = stack[-1] # 将当前索引入栈 stack.append(i) # 3. 遍历 j，寻找可能的三元组并计算最小跨度 min_span = float('inf') for j in range(1, n-1): # j 从 1 到 n-2 i = left_min_idx[j-1] # j 左侧最小值的索引 k = right_smaller_idx[j] # j 右侧第一个较小值的索引 # 检查三元组条件： nums[j] > nums[i] 且 k 存在 if nums[j] > nums[i] and k != -1: span = k - i if span < min_span: min_span = span # 4. 返回结果 return min_span if min_span != float('inf') else -1 # 测试用例 if __name__ == "__main__": # 示例 1 nums1 = [3, 5, 4, 7, 2, 1] print(f"输入: {nums1}") print(f"输出: {find_min_span(nums1)}") # 应输出 2 # 解释: 满足条件的三元组是 (0, 1, 2), 其中 i=0, j=1, k=2, nums[1]=5 > nums[0]=3 且 > nums[2]=4, k-i=2. # 示例 2 nums2 = [4, 3, 2, 1] print(f"\n输入: {nums2}") print(f"输出: {find_min_span(nums2)}") # 应输出 -1 # 解释: 数组递减，没有任何位置 j 能同时满足左侧有更小值且右侧有更小值。 # 更复杂的测试用例 nums3 = [1, 2, 3, 4, 5] print(f"\n输入: {nums3}") print(f"输出: {find_min_span(nums3)}") # 应输出 -1 # 解释: 数组递增，对于任何 j，其左侧最小值是 nums[0]=1，但右侧找不到比 nums[j] 小的数。 nums4 = [5, 4, 3, 2, 1, 6, 5, 4] print(f"\n输入: {nums4}") print(f"输出: {find_min_span(nums4)}") # 可以计算验证 ``` ### 关键步骤说明与复杂度分析 | 步骤 | 技术描述 | 时间复杂度 | 空间复杂度 | | :--- | :--- | :--- | :--- | | **预处理左侧最小索引** | 一次正向遍历，动态比较并记录到当前位置为止的最小值索引。 | O(n) | O(n) | | **预处理右侧较小值索引** | 使用单调栈进行一次反向遍历。栈维护了索引及其对应值的递增关系，能快速找到右侧第一个更小值。 | O(n) | O(n) (栈空间最坏为 O(n)) | | **主遍历与结果计算** | 遍历每个可能的 `j`，通过查表 O(1) 获取 `i` 和 `k`，并进行条件判断。 | O(n) | O(1) (不计预处理数组) | | **总计** | 三次线性遍历，无嵌套循环。 | **O(n)** | **O(n)** | 此方案严格满足了题目的性能要求，并能正确处理边界情况（如数组长度不足、单调数组等）。`left_min_idx` 确保了对于每个 `j`，我们都能以 O(1) 的时间获得其左侧最小值的**最优候选** `i`。`right_smaller_idx` 通过单调栈的预处理，同样以 O(1) 的时间提供了每个 `j` 右侧满足 `nums[k] < nums[j]` 的**最近候选** `k`。两者的结合使得我们能在 O(n) 时间内完成所有有效三元组的探索。