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

动态规划预处理+滑动窗口：力扣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;
    }
};