侧边栏壁纸
博主头像
GabrielxD

列車は必ず次の駅へ。では舞台は?私たちは?

  • 累计撰写 471 篇文章
  • 累计创建 108 个标签
  • 累计收到 9 条评论

目 录CONTENT

文章目录

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

GabrielxD
2022-09-26 / 0 评论 / 0 点赞 / 26 阅读 / 920 字 / 正在检测是否收录...

题目

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,nk)[k, n-k),那么 [0,nk1)[0, n-k-1) 范围元素的递增与否、 [k+1,n1)[k+1, n-1) 范围元素的递减与否就决定了中间的下标能否成为好下标。

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

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

  • 处于 [0,nk1)[0, n-k-1) 的下标为 a-1a 的元素呈非递增时,会导致 [a+1,a+k)[a+1, a+k) 区间的下标不能成为好下标。
  • 处于 [k+1,n1)[k+1, n-1) 的下标为 bb+1 的元素呈非递增时,会导致 (bk,b1](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;
    }
};
0

评论区