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

方法一：动态规划

思路

下标 i 是好下标需满足：下标 i 前连续 k 个元素都是非递增与下标 i 后连续 k 个元素都是非递减。只需要预先计算出下标 i 前元素连续非递增的个数以及下标 i 后元素连续非递减的个数即可判断下标 i 是否为好下标。对于下标 j，设下标 j 及之前元素连续非递增的个数为 left}j，下标 j 及之后元素连续非递减的个数为 right}j。当下标 i 同时满足 left}{i - 1} \ge k,\textit{right}{i + 1} \ge k 时，下标 i 为好下标。计算连续非递增和非递减的个数的方法如下：

• 如果下标 i 的元素小于等于下标 i-1 的元素，假设已知下标 i-1 及之前有 j 个元素连续非递增，则此时满足 nums}{i-1} \le \textit{nums}{i-2} \cdots \le \textit{nums}{i-j，已知 nums}i \le \textit{nums}{i-1，可推出 nums}{i} \le \textit{nums}{i-1} \cdots \le \textit{nums}{i-j，则此时 left}i = j + 1 = \textit{left}{i-1} + 1；如果下标 i 的元素大于下标 i-1 的元素，则此时 left}_i = 1。

• 如果下标 i 的元素小于等于下标 i+1 的元素，假设已知下标 i+1 及之后有 j 个元素连续非递减，则此时满足 nums}{i+1} \le \textit{nums}{i+2} \cdots \le \textit{nums}{i+j，已知 nums}i \le \textit{nums}{i+1，可推出 nums}{i} \le \textit{nums}{i+1} \cdots \le \textit{nums}{i+j，则此时 right}i = j + 1 = \textit{right}{i+1} + 1；如果下标 i 的元素大于下标 i+1 的元素，则此时 right}_i = 1。

依次检测所有的下标，即可得到所有好下标。

代码

[sol1-Python3]

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]

[sol1-Java]

class Solution {
    public List<Integer> goodIndices(int[] nums, int k) {
        int n = nums.length;
        int[] left = new int[n];
        int[] right = new int[n];
        Arrays.fill(left, 1);
        Arrays.fill(right, 1);
        for (int 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;
            }
        }

        List<Integer> ans = new ArrayList<>();
        for (int i = k; i < n - k; i++) {
            if (left[i - 1] >= k && right[i + 1] >= k) {
                ans.add(i);    
            }
        }
        return ans;
    }
}

[sol1-C++]

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> left(n, 1);
        vector<int> right(n, 1);
        for (int 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;
            }
        }

        vector<int> ans;
        for (int i = k; i < n - k; i++) {
            if (left[i - 1] >= k && right[i + 1] >= k) {
                ans.emplace_back(i);
            }
        }
        return ans;
    }
};

[sol1-C#]

public class Solution {
    public IList<int> GoodIndices(int[] nums, int k) {
        int n = nums.Length;
        int[] left = new int[n];
        int[] right = new int[n];
        Array.Fill(left, 1);
        Array.Fill(right, 1);
        for (int 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;
            }
        }

        IList<int> ans = new List<int>();
        for (int i = k; i < n - k; i++) {
            if (left[i - 1] >= k && right[i + 1] >= k) {
                ans.Add(i);    
            }
        }
        return ans;
    }
}

[sol1-C]

int* goodIndices(int* nums, int numsSize, int k, int* returnSize) {
    int * left = (int *)malloc(sizeof(int) * numsSize);
    int * right = (int *)malloc(sizeof(int) * numsSize);
    memset(left, 0, sizeof(int) * numsSize);
    memset(right, 0, sizeof(int) * numsSize);
    for (int i = 0; i < numsSize; i++) {
        left[i] = right[i] = 1;
    }
    for (int i = 1; i < numsSize; i++) {
        if (nums[i] <= nums[i - 1]) {
            left[i] = left[i - 1] + 1;
        }
        if (nums[numsSize - i - 1] <= nums[numsSize - i]) {
            right[numsSize - i - 1] = right[numsSize - i] + 1;
        }
    }

    int * ans = (int *)malloc(sizeof(int) * numsSize);
    int pos = 0;
    for (int i = k; i < numsSize - k; i++) {
        if (left[i - 1] >= k && right[i + 1] >= k) {
            ans[pos++] = i;
        }
    }
    free(left);
    free(right);
    *returnSize = pos;
    return ans;
}

[sol1-JavaScript]

var goodIndices = function(nums, k) {
    const n = nums.length;
    const left = new Array(n).fill(1);
    const right = new Array(n).fill(1);
    for (let 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;
        }
    }

    const ans = [];
    for (let i = k; i < n - k; i++) {
        if (left[i - 1] >= k && right[i + 1] >= k) {
            ans.push(i);    
        }
    }
    return ans;
};

[sol1-Golang]

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
}

复杂度分析

• 时间复杂度：O(n)，其中 n 为数组 nums 的长度。需要遍历数组求出下标 i 及之前连续非递增的个数与下标 i 及之后连续非递减的个数，然后再遍历数组检测下标 i 是否为好下标。

• 空间复杂度：O(n)，其中 n 为数组 nums 的长度。需要 O(n) 的空间来存储下标 i 及之前连续非递增的个数与下标 i 及之后连续非递减的个数。