【枚举】找到所有好下标【力扣第 312 场周赛】

题目

6190. 找到所有好下标

---

给你一个大小为 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^5
• 1 <= nums[i] <= 10^6
• 1 <= k <= n / 2

解题

方法一：枚举

思路

这题我们可以反向思考：通过前部分元素的递增与否与后部分元素的递减与否反推出好下标。
具体来说：好下标可能的范围是 $[k, n-k)$，那么 $[0, n-k-1)$ 范围元素的递增与否、 $[k+1, n-1)$ 范围元素的递减与否就决定了中间的下标能否成为好下标。

比如说：[2,1,1,1,3,4,1] 中，可能成为好下标的有 (2, 3, 4)。
但是我们发现 nums[4]=3，nums[5]=4 处于 $[3, 6)$ 的范围而非递减，于是就辐射式的导致左边 $(3, 4]$ 不能成为好下标(注意不包括 $3$)，于是好下标仅剩了 $(2, 3)$。

通过这个例子我们也发现：

• 处于 $[0, n-k-1)$ 的下标为 a-1 与 a 的元素呈非递增时，会导致 $[a+1, a+k)$ 区间的下标不能成为好下标。
• 处于 $[k+1, n-1)$ 的下标为 b 与 b+1 的元素呈非递增时，会导致 $(b-k, b-1]$ 区间的下标不能成为好下标。

于是我们枚举这两部分的元素进行比较并维护还成立的好下标即可。

代码

class Solution {
    public List<Integer> goodIndices(int[] nums, int k) {
        List<Integer> ans = new ArrayList<>();
        int n = nums.length;
        boolean[] flags = new boolean[n];
        for (int i = 1; i < n - k - 1; ++i) {
            if (nums[i - 1] < nums[i]) {
                for (int j = i + 1; j < i + k; ++j) flags[j] = true;
            }
        }
        for (int i = k + 1; i < n - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                for (int j = i - 1; j > i - k; --j) flags[j] = true;
            }
        }
        for (int i = k; i < n - k; ++i) {
            if (!flags[i]) ans.add(i);
        }
        return ans;
    }
}

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        bool flags[n];
        memset(flags, 0, sizeof(flags));
        for (int i = 1; i < n - k - 1; ++i) {
            if (nums[i - 1] < nums[i]) {
                for (int j = i + 1; j < i + k; ++j) flags[j] = true;
            }
        }
        for (int i = k + 1; i < n - 1; ++i) {
            if (nums[i] > nums[i + 1]) {
                for (int j = i - 1; j > i - k; --j) flags[j] = true;
            }
        }
        vector<int> ans;
        for (int i = k; i < n - k; ++i) {
            if (!flags[i]) ans.push_back(i);
        }
        return ans;
    }
};