Question

2420. 找到所有好下标

English Version

题目描述

给你一个大小为 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$ 为数组长度。

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]

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;
  }
}

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;
  }
};

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
}