【Leetcode】2100. Find Good Days to Rob the Bank

题目地址：

https://leetcode.com/problems/find-good-days-to-rob-the-bank/description/

给定一个长$n$数组$A$，再给定一个非负整数$t$，求所有的满足下面条件的下标$i$：$A[i-t]\ge A[i-t+1]\ge ...\ge A[i]\le A[i+1]\le ...\le A[i+t]$。

设$f[i]$是以$A[i]$为结尾的最长非严格下降子数组的长度，设$g[i]$是以$A[i]$为开头的最长非严格上升子数组的长度，那么当 min ⁡ { f [ i ] , g [ i ] } ≥ t + 1 \min\{f[i],g[i]\}\ge t+1 min{f[i],g[i]}≥t+1的时候，$i$满足条件。代码如下：

class Solution {
 public:
  vector<int> goodDaysToRobBank(vector<int>& v, int t) {
    int n = v.size();
    vector<int> left(n), right(n);
    for (int i = 0; i < n; i++)
      if (!i || v[i - 1] < v[i]) left[i] = 1;
      else left[i] = 1 + left[i - 1];

    for (int i = n - 1; i >= 0; i--)
      if (i == n - 1 || v[i + 1] < v[i]) right[i] = 1;
      else right[i] = 1 + right[i + 1];

    vector<int> res;
    for (int i = 0; i < v.size(); i++)
      if (min(left[i], right[i]) >= t + 1) res.push_back(i);

    return res;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

时空复杂度$O(n)$。