题目描述
给你一个大小为 n
下标从 0 开始的整数数组 nums
和一个正整数 k
。
对于 k <= i < n - k
之间的一个下标 i
,如果它满足以下条件,我们就称它为一个 好 下标:
- 下标
i
之前 的k
个元素是 非递增的。 - 下标
i
之后 的k
个元素是 非递减的。
按 升序 返回所有好下标。
样例
输入:nums = [2,1,1,1,3,4,1], k = 2
输出:[2,3]
解释:数组中有两个好下标:
- 下标 2。子数组 [2,1] 是非递增的,子数组 [1,3] 是非递减的。
- 下标 3。子数组 [1,1] 是非递增的,子数组 [3,4] 是非递减的。
注意,下标 4 不是好下标,因为 [4,1] 不是非递减的。
输入:nums = [2,1,1,2], k = 2
输出:[]
解释:数组中没有好下标。
限制
n == nums.length
3 <= n <= 10^5
1 <= nums[i] <= 10^6
1 <= k <= n / 2
算法
(线性扫描) $O(n)$
- 先反向线性扫描,找到所有后续 $k$ 个元素满足条件的位置。
- 然后正向线性扫描,对所有前序 $k$ 个元素满足标记的位置,判断后续是否也满足条件;如果都满足则记录答案。
时间复杂度
- 遍历数组两次,故时间复杂度为 $O(n)$。
空间复杂度
- 需要 $O(n)$ 的额外空间存储后续满足条件的位置。
C++ 代码
class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k) {
const int n = nums.size();
vector<bool> post(n, false);
for (int i = n - 2, j = 1; i >= 0; i--) {
if (j >= k)
post[i] = true;
if (nums[i] <= nums[i + 1]) j++;
else j = 1;
}
vector<int> ans;
for (int i = 1, j = 1; i < n; i++) {
if (j >= k && post[i])
ans.push_back(i);
if (nums[i] <= nums[i - 1]) j++;
else j = 1;
}
return ans;
}
};