找到所有好下标

给你一个大小为 n 下标从 0 开始的整数数组 nums 和一个正整数 k 。

对于 k <= i < n - k 之间的一个下标 i ，如果它满足以下条件，我们就称它为一个 好 下标：

下标 i 之前 的 k 个元素是 非递增的 。
下标 i 之后 的 k 个元素是 非递减的 。
按 升序 返回所有好下标。

---

考点：最长上升子序列的变形题目。

首先题目所说的非递增和非递减都是最长上升子序列模型可以求出来的。唯一的区别就是这道题目要求的子序列是连续的，而最长上升子序列要求的子序列是可以不连续的。

因此思路就出来了，把整一个序列的最长下降连续子序列求出来。在倒着求一下整一个序列的最长下降连续子序列求出来。然后枚举每一个交点，看一下哪一些点符合要求，符合要求的就是答案。

我们可以看一下最长上升子序列的代码和这里求最长连续上升子序列的代码有什么不一样。

这是最长上升连续子序列

for(int i = 0; i < n; i++)
{
    f[i] = 1;
    if(i && nums[i] <= nums[i - 1])
        f[i] = f[i - 1] + 1;
}

这是最长上升子序列

for(int i = 0; i < n; i++)
{
    f[i] = 1;
    for(int j = 0; j <= i; j++)
    	if(s[j] < s[i])
    		f[i] = max(f[j] + 1, f[i]);
}

很明显，由于不需要连续，最长上升子序列需要把每一个以j结尾的序列都比较一遍，而最长上升连续子序列不需要。

下面是ac代码：

class Solution {
public:
    vector<int> goodIndices(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> f(n), g(n);

        for(int i = 0; i < n; i++)
        {
            f[i] = 1;
            if(i && nums[i] <= nums[i - 1])
                f[i] = f[i - 1] + 1;
        }

        for(int i = n - 1; i >= 0; i--)
        {
            g[i] = 1;
            if(i < n - 1 && nums[i] <= nums[i + 1])
                g[i] = g[i + 1] + 1;
        }

        vector<int> res;
        for(int i = 0; i < n; i++)
            if(i && i < n - 1 && f[i - 1] >= k && g[i + 1] >= k)
                res.push_back(i);
        return res;
    }
};

同类题目：登山
思路是一模一样的，只是一个是连续的子数组一个不连续罢了。