一、问题理解
题目要求找出数组中满足特定条件的"好下标":对于下标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;
}
};
三、关键点分析
四、复杂度分析
- 时间复杂度:O(n) 三次线性遍历
- 空间复杂度:O(n) 需要两个辅助数组
五、实际应用
这种预处理+滑动窗口的组合方法在解决数组区间问题时非常高效,类似的思路可以应用于:
- 股票买卖问题
- 雨水收集问题
- 最大子数组问题