class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k) {
}
};
2420. 找到所有好下标
给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。
对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：
i 之前 的 k 个元素是 非递增的 。i 之后 的 k 个元素是 非递减的 。按 升序 返回所有好下标。
示例 1：
输入：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] 不是非递减的。
示例 2：
输入：nums = [2,1,1,2], k = 2 输出：[] 解释：数组中没有好下标。
提示：
n == nums.length3 <= n <= 1051 <= nums[i] <= 1061 <= k <= n / 2原站题解
golang 解法, 执行用时: 112 ms, 内存消耗: 9.9 MB, 提交时间: 2022-11-21 15:29:43
func goodIndices(nums []int, k int) (ans []int) {
n := len(nums)
left := make([]int, n)
right := make([]int, n)
for i := 0; i < n; i++ {
left[i] = 1
right[i] = 1
}
for i := 1; i < n; i++ {
if nums[i] <= nums[i-1] {
left[i] = left[i-1] + 1
}
if nums[n-i-1] <= nums[n-i] {
right[n-i-1] = right[n-i] + 1
}
}
for i := k; i < n-k; i++ {
if left[i-1] >= k && right[i+1] >= k {
ans = append(ans, i)
}
}
return
}
python3 解法, 执行用时: 292 ms, 内存消耗: 30.8 MB, 提交时间: 2022-11-21 15:29:28
class Solution:
def goodIndices(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
left = [1] * n
right = [1] * n
for i in range(1, n):
if nums[i] <= nums[i - 1]:
left[i] = left[i - 1] + 1
if nums[n - i - 1] <= nums[n - i]:
right[n - i - 1] = right[n - i] + 1
return [i for i in range(k, n - k) if left[i - 1] >= k and right[i + 1] >= k]