动态规划预处理+滑动窗口：力扣2420题"好下标"解法详解

ftggdnt

一、问题理解

题目要求找出数组中满足特定条件的"好下标"：对于下标i，其左侧k个元素必须是非递增的，右侧k个元素必须是非递减的。这是典型的数组区间性质检查问题。

二、解题思路1. 动态规划预处理

核心思想是通过两次预处理：

• left数组：记录每个位置向左的非递增序列长度
• right数组：记录每个位置向右的非递减序列长度
  
  

2. 完整代码解析

1. class Solution {
   
2. public:
   
3.     vector<int> goodIndices(vector<int>& nums, int k) {
   
4.         int n = nums.size();
   
5.         vector<int> res;
   
6.         vector<int> left(n, 1);  // 初始化：每个元素至少可以形成长度为1的序列
   
7.         vector<int> right(n, 1); // 同上
   
8.         
   
9.         // 从左到右预处理left数组
   
10.         for (int i = 1; i < n; ++i) {
    
11.             if (nums[i] <= nums[i-1]) {
    
12.                 left[i] = left[i-1] + 1; // 满足条件时继承前一个位置的长度+1
    
13.             }
    
14.         }
    
15.         
    
16.         // 从右到左预处理right数组
    
17.         for (int i = n-2; i >= 0; --i) {
    
18.             if (nums[i] <= nums[i+1]) {
    
19.                 right[i] = right[i+1] + 1; // 同理处理右侧
    
20.             }
    
21.         }
    
22.         
    
23.         // 滑动窗口检查有效下标
    
24.         for (int i = k; i < n - k; ++i) {
    
25.             // 检查左右两侧是否都满足k长度要求
    
26.             if (left[i-1] >= k && right[i+1] >= k) {
    
27.                 res.push_bACk(i);
    
28.             }
    
29.         }
    
30.         
    
31.         return res;
    
32.     }
    
33. };

复制代码

三、关键点分析

• 预处理优化：O(n)时间完成两次遍历，避免每次检查都重复计算
• 边界处理：注意i的取值范围是[k, n-k-1]
• 空间换时间：使用两个额外数组存储中间结果
  
  

四、复杂度分析

• 时间复杂度：O(n) 三次线性遍历
• 空间复杂度：O(n) 需要两个辅助数组
  
  

五、实际应用

这种预处理+滑动窗口的组合方法在解决数组区间问题时非常高效，类似的思路可以应用于：

• 股票买卖问题
• 雨水收集问题
• **子数组问题
  
  

来源：动态规划预处理+滑动窗口：力扣2420题"好下标"解法详解