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

一、问题理解

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

二、解题思路

1. 动态规划预处理

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

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

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

2. 完整代码解析

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;
        vector<int> left(n, 1);  // 初始化：每个元素至少可以形成长度为1的序列
        vector<int> right(n, 1); // 同上
        
        // 从左到右预处理left数组
        for (int i = 1; i < n; ++i) {
            if (nums[i] <= nums[i-1]) {
                left[i] = left[i-1] + 1; // 满足条件时继承前一个位置的长度+1
            }
        }
        
        // 从右到左预处理right数组
        for (int i = n-2; i >= 0; --i) {
            if (nums[i] <= nums[i+1]) {
                right[i] = right[i+1] + 1; // 同理处理右侧
            }
        }
        
        // 滑动窗口检查有效下标
        for (int i = k; i < n - k; ++i) {
            // 检查左右两侧是否都满足k长度要求
            if (left[i-1] >= k && right[i+1] >= k) {
                res.push_bACk(i);
            }
        }
        
        return res;
    }
};

三、关键点分析

1. 预处理优化：O(n)时间完成两次遍历，避免每次检查都重复计算

2. 边界处理：注意i的取值范围是[k, n-k-1]

3. 空间换时间：使用两个额外数组存储中间结果

四、复杂度分析

• 时间复杂度：O(n) 三次线性遍历

• 空间复杂度：O(n) 需要两个辅助数组

五、实际应用

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

• 股票买卖问题

• 雨水收集问题

• 最大子数组问题

参考：信奥自学