跳到主要内容

2100.适合野炊的日子

链接：2100.适合野炊的日子
难度：Medium
标签：数组、动态规划、前缀和
简介：请你返回一个数组，包含 所有 适合打劫银行的日子（下标从 0 开始）。返回的日子可以 任意 顺序排列。

题解 1 - cpp​

  • 编辑时间：2022-03-06
  • 执行用时：116ms
  • 内存消耗：84.8MB
  • 编程语言：cpp
  • 解法介绍：记录当前值左侧最大递增长度和右侧最大递增长度。
class Solution {
        public:
         vector<int> goodDaysToRobBank(vector<int>& security, int time) {
             int n = security.size();
             vector<int> cnts(n, 0);
             for (int i = n - 2; i >= 0; i--) {
                 if (security[i] <= security[i + 1]) {
                     cnts[i] = cnts[i + 1] + 1;
                 } else {
                     cnts[i] = 0;
                 }
             }
             vector<int> ans;
             int prev = 0;
             for (int i = 0; i < n; i++) {
                 if (i > 0 && security[i] <= security[i - 1]) {
                     prev++;
                 } else {
                     prev = 0;
                 }
                 if (prev >= time && cnts[i] >= time) {
                     ans.push_back(i);
                 }
             }
             return ans;
         }
     };