难度: Medium
给你一个大小为 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运行时间: 87 ms
内存: 27.7 MB
class Solution:
def goodIndices(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
if k == 1:
return [i for i in range(1, n-1)]
result = list()
left, right, cur = 0, k+1, 1
while True:
if right >= n-1:
break
if nums[left+1] <= nums[left] and nums[right+1] >= nums[right]:
cur += 1
left += 1
right += 1
if cur >= k:
result.append(left+1)
else:
cur = 1
left += 1
right += 1
return result
解题思路主要是通过一次遍历来检查每一个可能的好下标。首先，初始化三个指针：left、right 和 cur。left 和 right 分别代表检查非递增和非递减子数组的起始位置。cur 用于计数连续满足条件的元素个数。遍历过程中，如果当前的元素满足非递增和非递减的条件，cur 递增并移动 left 和 right。当 cur 达到 k 时，说明找到了一个好下标并将其加入结果列表。如果条件被打破，cur 重置为 1。这种方法避免了多次重复检查子数组的情况。
时间复杂度: O(n)
空间复杂度: O(1)
# 增加了注释的题解代码
class Solution:
def goodIndices(self, nums: List[int], k: int) -> List[int]:
n = len(nums)
# 处理 k=1 的特殊情况，理论上不会出现因为 k 最小为 1 且 n 最小为 3
if k == 1:
return [i for i in range(1, n-1)]
result = list()
left, right, cur = 0, k+1, 1
# 使用滑动窗口检查每个可能的好下标
while True:
# 当右指针到达数组末尾前，停止循环
if right >= n-1:
break
# 检查当前元素是否满足非递增和非递减的条件
if nums[left+1] <= nums[left] and nums[right+1] >= nums[right]:
cur += 1
left += 1
right += 1
# 如果连续满足条件的元素个数达到 k，记录为好下标
if cur >= k:
result.append(left+1)
else:
# 如果不满足条件，重置 cur
cur = 1
left += 1
right += 1
return result
滑动窗口的策略基于两个主要的指针：left和right，其中right指针负责探索数组的向右边界，而left指针随着right的推进同时推进。由于right指针会从k+1起始，确保其遍历数组直到倒数第二个元素之前，这样就能够覆盖所有可能的好下标位置。每次循环中，left和right指针都会同步向右移动，确保数组中的每个元素都被考虑到，因此不会错过任何一个可能的好下标。
一旦连续满足条件的元素个数达到k，相应的下标会被记录为好下标。如果在此之后的下一次迭代中条件不再满足，即nums[left+1] > nums[left]或nums[right+1] < nums[right]，则cur（当前连续满足条件的长度）会被重置为1，同时left和right指针会同步向右移动一位。这意味着，每次条件不满足时，都会从新的位置开始重新计数，以寻找新的可能的好下标。
在题解的逻辑中，如果在遍历过程中遇到不满足非递增或非递减条件的情况，`cur`（当前连续满足条件的元素个数）会被立即重置为1。同时，left和right指针也会同步向右移动一位，从而开始新的检查周期。这种重置逻辑确保只有连续满足条件的元素序列才会被考虑为好下标的候选，一旦发现不符合条件的元素，之前的计数将不被考虑，且从新的起点开始重新计数。
确实，按照题解中的逻辑，当right指针达到数组的倒数第二个元素时，循环将停止。这意味着数组的最后几个元素不会作为好下标的起始点来考虑。在实际实现中，由于需要检查以每个元素为起始点的k个元素是否满足非递增或非递减条件，所以在接近数组末尾时可能无法形成完整的k长度的子数组，因此这些元素不会被算作好下标起始点。