思路:前后缀分解
时间复杂度:O(n)
理解:
- 新开两个数组
vector<int> l
和vector<int> r
; - r 数组记录的是,以第 i 个位置为第一一个数,递增的长度;
- l 数组记录的是,以第 i 个位置为最后一个数,递减的长度;
类似的题目:
最大的和 https://www.acwing.com/problem/content/1053/
对应的题解: https://www.acwing.com/solution/content/139282/
代码实现:
class Solution {
public:
vector<int> goodIndices(vector<int>& nums, int k)
{
int n = nums.size();
if(n == 1) return {1};
// r 数组记录的是,以第 i 个位置为第一一个数,递增的长度
vector<int> l(n), r(n); // l 数组记录的是,以第 i 个位置为最后一个数,递减的长度
for(int i = 0; i < n; i++)
{
l[i] = 1;
// i 的范围上面已经小于 n 了,所以保证 i - 1 >= 0
if(i - 1 >= 0 && nums[i - 1] >= nums[i]) l[i] = l[i - 1] + 1; // 递减
}
for(int i = n - 1; i >= 0; i--)
{
r[i] = 1;
// i 的范围上面已经 i >= 0 了,所以保证 i + 1 < n
if(i + 1 < n && nums[i] <= nums[i + 1]) r[i] = r[i + 1] + 1; // 递增
}
vector<int> ans;
for(int i = k; i < n - k; i++)
if(l[i - 1] >= k && r[i + 1] >= k)
ans.push_back(i);
return ans;
}
// bool my_cmp(int x, int y)
// {
// return x > y;
// }
// vector<int> goodIndices(vector<int>& nums, int k)
// {
// vector<int> ans;
// int n = nums.size();
// if(k * 2 == n) return {};
// for(int i = k; i < n - k; i++)
// {
// // bool flag = true;
// // for(int j = i - k + 1; j < i; j++)
// // if(nums[j - 1] < nums[j])
// // {
// // flag = false;
// // break;
// // }
// //bool flag = is_sorted(nums.begin() + i - k, nums.begin() + i - 1, greater<int>()); // 是降序就返回 true
// // if(flag == true) continue;
// // for(int j = i + 1 + 1; j <= i + k; j++) // j <= i + k
// // if(nums[j - 1] > nums[j])
// // {
// // flag = false;
// // break;
// // }
// // is_sorted(v.begin(),v.end(),greater<int>());
// // bool is = is_sorted(nums.begin() + i + 1, nums.begin() + i + k); // 是升序就返回 true
// // if(flag == true && is == true) ans.push_back(i);
// //cout << flag << ' ' << is << ' ' << i - k << ' ' << i - 1 << ' ' << i + 1 << ' ' << i + k << endl;
// }
// return ans;
// }
};