跳转至

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.length
  • 3 <= n <= 105
  • 1 <= nums[i] <= 106
  • 1 <= k <= n / 2

解法

方法一：递推

我们定义两个数组 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
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]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        int[] decr = new int[n];
        int[] incr = new int[n];
        Arrays.fill(decr, 1);
        Arrays.fill(incr, 1);
        for (int i = 2; i < n - 1; ++i) {
            if (nums[i - 1] <= nums[i - 2]) {
                decr[i] = decr[i - 1] + 1;
            }
        }
        for (int i = n - 3; i >= 0; --i) {
            if (nums[i + 1] <= nums[i + 2]) {
                incr[i] = incr[i + 1] + 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = k; i < n - k; ++i) {
            if (decr[i] >= k && incr[i] >= k) {
                ans.add(i);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> decr(n, 1);
        vector<int> incr(n, 1);
        for (int i = 2; i < n; ++i) {
            if (nums[i - 1] <= nums[i - 2]) {
                decr[i] = decr[i - 1] + 1;
            }
        }
        for (int i = n - 3; ~i; --i) {
            if (nums[i + 1] <= nums[i + 2]) {
                incr[i] = incr[i + 1] + 1;
            }
        }
        vector<int> ans;
        for (int i = k; i < n - k; ++i) {
            if (decr[i] >= k && incr[i] >= k) {
                ans.push_back(i);
            }
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
func goodIndices(nums []int, k int) []int {
    n := len(nums)
    decr := make([]int, n)
    incr := make([]int, n)
    for i := range decr {
        decr[i] = 1
        incr[i] = 1
    }
    for i := 2; i < n; i++ {
        if nums[i-1] <= nums[i-2] {
            decr[i] = decr[i-1] + 1
        }
    }
    for i := n - 3; i >= 0; i-- {
        if nums[i+1] <= nums[i+2] {
            incr[i] = incr[i+1] + 1
        }
    }
    ans := []int{}
    for i := k; i < n-k; i++ {
        if decr[i] >= k && incr[i] >= k {
            ans = append(ans, i)
        }
    }
    return ans
}

评论