当前位置：首页 > news >正文

【C++前缀和】2420. 找到所有好下标|1695

news 2025/4/22 2:27:25

本文涉及的基础知识点

C++算法：前缀和、前缀乘积、前缀异或的原理、源码及测试用例包括课程视频
C++前后缀分解

LeetCode2420. 找到所有好下标

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

C++ 前缀和

preSum0[i]记录以nums[i]开头的最长非递减子数组的长度。
$\begin{cases} preSum0[i] = preSum0[i+1]+1 && nums[i] <= nums[i+1] \\ preSum0[i] = 1 && other \\ \end{cases}$
preSum1[i]记录以nums[i]结尾的最长非递增子数组长度。
$\begin{cases} preSum1[i] = preSum1[i-1]+1 && nums[i-1] >= nums[i] \\ preSum1[i] = 1 && other \\ \end{cases}$

代码

核心代码

	class Solution {public:vector<int> goodIndices(vector<int>& nums, int k) {const int N = nums.size();vector<int> preSum0(N, 1),preSum1(N,1);for (int i = N - 2; i >= 0; i--) {if (nums[i] <= nums[i + 1]) {preSum0[i] = preSum0[i + 1] + 1;}}for (int i = 1; i < N; i++) {if (nums[i - 1] >= nums[i]) {preSum1[i] = preSum1[i - 1] + 1;}}vector<int> ret;for (int i = k; i + k < N; i++) {if ((preSum0[i + 1] >= k) && (preSum1[i - 1] >= k)) {ret.emplace_back(i);}}return ret;}};

单元测试

vector<int> nums;int k;TEST_METHOD(TestMethod11){nums = { 2,1,1,1,3,4,1 }, k = 2;auto res = Solution().goodIndices(nums, k);AssertEx(vector<int>{2, 3}, res);}TEST_METHOD(TestMethod12){nums = { 2,1,1,2 }, k = 2;auto res = Solution().goodIndices(nums, k);AssertEx(vector<int>{}, res);}

扩展阅读

我想对大家说的话
工作中遇到的问题，可以按类别查阅鄙人的算法文章，请点击《算法与数据汇总》。
学习算法：按章节学习《喜缺全书算法册》，大量的题目和测试用例，打包下载。重视操作
有效学习：明确的目标及时的反馈拉伸区（难度合适）专注
闻缺陷则喜(喜缺)是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛
失败+反思=成功成功+反思=成功