What is the main strategy for Find All Good Indices?

Use state transition dynamic programming to precompute non-increasing prefixes and non-decreasing suffixes, then scan for indices satisfying both conditions.

Can this be solved without extra space?

Yes, but it complicates checking previous and next k elements; the DP arrays provide clearer O(n) solution.

How do you handle equal consecutive elements?

Equal elements count as non-increasing or non-decreasing, so include them when computing prefix and suffix lengths.

What is the time complexity for large arrays?

With prefix and suffix precomputation, the algorithm runs in O(n) time, suitable for n up to 10^5.

Why is this pattern called state transition dynamic programming?

Because each element's prefix or suffix length depends on the previous element's state, forming a chain of transitions.

#2420

Medium

auto_awesome状态·转移·动态规划

LeetCode 题解工作台

找到所有好下标

给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。对于 k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个好下标：下标 i 之前的 k 个元素是非递增的。下标 i 之后的 k 个元素是非递减的。按升序返回所有好下标。示例 1：输…

数组动态规划前缀和

题目描述

给你一个大小为 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.length
3 <= n <= 10⁵
1 <= nums[i] <= 10⁶
1 <= k <= n / 2

lightbulb

解题思路

方法一：递推

我们定义两个数组 decr 和 incr，分别表示从左到右和从右到左的非递增和非递减的最长子数组长度。

遍历数组，更新 decr 和 incr 数组。

然后顺序遍历下标 $i$ （其中 $k\le i \lt n - k$ ），若 $decr[i] \geq k$ 并且 $incr[i] \geq k$ ，则 $i$ 为好下标。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def goodIndices(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        decr = [1] * (n + 1)
        incr = [1] * (n + 1)
        for i in range(2, n - 1):
            if nums[i - 1] <= nums[i - 2]:
                decr[i] = decr[i - 1] + 1
        for i in range(n - 3, -1, -1):
            if nums[i + 1] <= nums[i + 2]:
                incr[i] = incr[i + 1] + 1
        return [i for i in range(k, n - k) if decr[i] >= k and incr[i] >= k]

speed

复杂度分析

指标	值
时间	complexity is O(n) because each element is visited once during prefix and suffix precomputations and once during the final scan. Space complexity is O(n) for storing prefix and suffix arrays.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate recognizes the pattern of using state transition dynamic programming for prefix and suffix computations.
question_mark
Candidate correctly handles edge indices where k-length prefix or suffix may not exist.
question_mark
Candidate produces a solution with linear time instead of checking all subarrays naively.

warning

常见陷阱

外企场景

error
Forgetting that the prefix or suffix must be exactly k elements and miscounting the lengths.
error
Using nested loops to check each subarray, causing TLE for large n.
error
Incorrectly handling non-increasing or non-decreasing conditions when consecutive equal elements appear.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Find all indices where prefix is strictly decreasing and suffix is strictly increasing.
arrow_right_alt
Determine good indices for k-length non-increasing and non-decreasing segments in a circular array.
arrow_right_alt
Compute the maximum number of good indices for a varying k value instead of a fixed k.

help

常见问题

外企场景

继续练习

#2439 最小化数组中的最大值 #2552 统计上升四元组 #2218 从栈中取出 K 个硬币的最大面值和