力扣2420题解：寻找满足条件的数组下标（C++动态规划解法与详细分析）

一、题目解读

力扣2420题要求在一个整数数组nums中，找到所有满足以下条件的下标i：以i为中心，向左和向右分别存在长度为k的非递增和非递减子数组。例如，若nums[i-1] ≤ nums[i] ≤ nums[i+1]且左右两侧长度均≥k，则i为有效下标。题目需返回所有符合条件的下标集合。

二、解题思路

采用动态规划思想，通过预处理两个辅助数组left和right，分别记录每个位置向左和向右的最长非递增/非递减子数组长度。核心思路如下：

1. 预处理left数组：从左到右遍历，若nums[i] ≤ nums[i-1]，则left[i] = left[i-1] + 1，否则重置为1；

2. 预处理right数组：从右到左遍历，若nums[i] ≤ nums[i+1]，则right[i] = right[i+1] + 1，否则重置为1；

3. 遍历中间位置：对于每个i（需满足i ≥ k && i < n - k），检查left[i-1] ≥ k && right[i+1] ≥ k，符合条件则加入结果。

此解法将O(n^2)的暴力判断优化为O(n)预处理+线性遍历，大幅降低时间复杂度。

三、解题步骤

1. 初始化：

    创建left和right数组，初始化所有元素为1（默认单个元素满足条件）。

2. 预处理left数组：

    从i=1开始，若nums[i] ≤ nums[i-1]，更新left[i] = left[i-1] + 1，否则保持left[i] = 1。

3. 预处理right数组：

    从i=n-2开始倒序，若nums[i] ≤ nums[i+1]，更新right[i] = right[i+1] + 1，否则保持right[i] = 1。

4. 筛选有效下标：

    遍历i=k到n-k-1，若left[i-1] ≥ k && right[i+1] ≥ k，将i加入结果数组。

通过分阶段处理，避免重复计算每个位置的长度，确保线性时间复杂度。

四、代码与注释

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> res;          // 结果下标集合
        vector<int> left(n, 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; // 继承左侧长度
            }
        }

        // 预处理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) {
            if (left[i-1] >= k && right[i+1] >= k) { // 左右均达标
                res.push_back(i);                   // 加入结果
            }
        }

        return res;
    }
};

五、总结

本解法通过动态规划预处理左右最长子数组长度，将复杂的条件判断转化为简单的线性扫描，核心优势在于：

1. 时空权衡：使用额外空间存储中间结果，换取时间复杂度从O(n^2)降至O(n)；

2. 边界处理：通过初始化left/right为1，避免单独处理单个元素的情况；

3. 逻辑清晰：分阶段处理left和right，降低代码耦合性。

适用于需要处理数组中局部区间条件的场景，建议进一步探索空间优化（如滚动数组）或二分加速的可能性。