本文涉及的基础知识点

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]开头的最长非递减子数组的长度。
{ p r e S u m 0 [ i ] = p r e S u m 0 [ i + 1 ] + 1 n u m s [ i ] < = n u m s [ i + 1 ] p r e S u m 0 [ i ] = 1 o t h e r \begin{cases} preSum0[i] = preSum0[i+1]+1 && nums[i] <= nums[i+1] \\ preSum0[i] = 1 && other \\ \end{cases} {preSum0[i]=preSum0[i+1]+1preSum0[i]=1​​nums[i]<=nums[i+1]other​
preSum1[i]记录以nums[i]结尾的最长非递增子数组长度。
{ p r e S u m 1 [ i ] = p r e S u m 1 [ i − 1 ] + 1 n u m s [ i − 1 ] > = n u m s [ i ] p r e S u m 1 [ i ] = 1 o t h e r \begin{cases} preSum1[i] = preSum1[i-1]+1 && nums[i-1] >= nums[i] \\ preSum1[i] = 1 && other \\ \end{cases} {preSum1[i]=preSum1[i−1]+1preSum1[i]=1​​nums[i−1]>=nums[i]other​

代码

核心代码

	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);
		}