前缀和思想
用数组 l[ ]表示前面有多少个数满足 a[i−1]>=a[i]
用数组 r[] 表示前面有多少个数满足 a[i]<=a[i+1]
O(n)遍历之后得到 l[] , r[]
然后O(n)找满足l [ i ] > = t i m e & & r [ i ] > = t i m e 的下标存入 vector 并返回
Code:
class Solution { public: vector<int> goodDaysToRobBank(vector<int>& security, int time) { int n = security.size(); vector<int> l(n), r(n); for(int i=1;i<n;i++) { if(security[i] <= security[i-1]) l[i] = l[i-1] + 1; if(security[n-i-1] <= security[n-i]) r[n-i-1] = r[n-i] + 1; // cout << l[i] << " " << r[i] << endl; } vector<int> ans; for(int i=time;i<n-time;i++) { if(l[i] >= time && r[i] >= time) ans.push_back(i); } return ans; } };
文章知识点与官方知识档案匹配，可进一步学习相关知识
算法技能树leetcode-动态规划22-括号生成8242 人正在系统学习中
