Medium

题目描述

给你一个大小为 n 的整数数组 nums 和一个正整数 k。

如果满足下述条件，我们称下标 i 在范围 k <= i < n - k 内是 好下标：

  • 下标 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^5
  • 1 <= nums[i] <= 10^6
  • 1 <= k <= n / 2

解题思路

这道题需要找到满足条件的好下标，关键在于高效地检查每个下标前后 k 个元素的单调性。

思路分析：

暴力解法是对每个可能的下标 i，分别检查其前 k 个和后 k 个元素的单调性，但这样时间复杂度为 O(n*k)，效率较低。

更优的解法是使用预处理的思想：

  1. 预计算每个位置向左连续多少个元素满足非递增关系
  2. 预计算每个位置向右连续多少个元素满足非递减关系

具体步骤：

  • 用 left[i] 表示从位置 i 开始向左连续的非递增元素个数
  • 用 right[i] 表示从位置 i 开始向右连续的非递减元素个数
  • 对于下标 i 是好下标的条件：left[i-1] >= k 且 right[i+1] >= k

这样只需要两次遍历预处理，然后一次遍历找出所有好下标，总时间复杂度为 O(n)。

推荐解法： 预处理 + 一次遍历，时间复杂度最优。

代码实现

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> left(n, 1), right(n, 1);
        
        // 计算每个位置向左的非递增长度
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i-1]) {
                left[i] = left[i-1] + 1;
            }
        }
        
        // 计算每个位置向右的非递减长度
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= nums[i+1]) {
                right[i] = right[i+1] + 1;
            }
        }
        
        vector<int> result;
        for (int i = k; i < n - k; i++) {
            if (left[i-1] >= k && right[i+1] >= k) {
                result.push_back(i);
            }
        }
        
        return result;
    }
};

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
        
        # 计算每个位置向右的非递减长度
        for i in range(n-2, -1, -1):
            if nums[i] <= nums[i+1]:
                right[i] = right[i+1] + 1
        
        result = []
        for i in range(k, n - k):
            if left[i-1] >= k and right[i+1] >= k:
                result.append(i)
        
        return result

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];
        
        // 初始化
        for (int i = 0; i < n; i++) {
            left[i] = 1;
            right[i] = 1;
        }
        
        // 计算每个位置向左的非递增长度
        for (int i = 1; i < n; i++) {
            if (nums[i] <= nums[i-1]) {
                left[i] = left[i-1] + 1;
            }
        }
        
        // 计算每个位置向右的非递减长度
        for (int i = n-2; i >= 0; i--) {
            if (nums[i] <= nums[i+1]) {
                right[i] = right[i+1] + 1;
            }
        }
        
        List<int> result = new List<int>();
        for (int i = k; i < n - k; i++) {
            if (left[i-1] >= k && right[i+1] >= k) {
                result.Add(i);
            }
        }
        
        return result;
    }
}

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;
        }
    }
    
    // 计算每个位置向右的非递减长度
    for (let i = n-2; i >= 0; i--) {
        if (nums[i] <= nums[i+1]) {
            right[i] = right[i+1] + 1;
        }
    }
    
    const result = [];
    for (let i = k; i < n - k; i++) {
        if (left[i-1] >= k && right[i+1] >= k) {
            result.push(i);
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度大小
时间复杂度O(n)
空间复杂度O(n)
  • 时间复杂度：O(n)，需要三次遍历数组，每次 O(n)
  • 空间复杂度：O(n)，需要额外的 left 和 right 数组存储预处理结果

相关题目