适合野炊的日子 图解题解

什么样的一天才算适合野炊的好日子

security[i] 是第 i 天的出行指数，再给整数 time。第 i 天适合野炊，要求前面连续 time 天非递增（一路不涨，持平也行）、后面连续 time 天非递减（一路不跌），像个谷底。题面例子 security=[5,3,3,3,5,6,2]、time=2，输出 [2,3]。

每天往两边各数 time 天，慢在哪里

候选天往左要比 time 对邻居、往右再比 time 对，n 天合计 O(n×time) 次比较（大 O 描述数据变大时操作次数怎么涨）。慢在重复：第 2 天验左肩比过那对 3 和 3，第 3 天又把同一对再比一遍——相邻两天的窗口几乎整段重叠。既然反复被要，先算一次存下来。

left 和 right 两把尺子各量什么

这就是动态规划（把『这天往左连跌了几天』这类小答案填进表，要用直接查）。left[i] 记第 i 天往左的连续非递增天数，right[i] 记往右的连续非递减天数；left 从左往右攒，right 从右往左攒，一前一后合称前后缀表。判定缩成：两边取短的也得够 time，time ≤ min(left[i], right[i])。

只和邻居比一次，整段趋势凭什么有保证

填表靠递推（用前一格推这一格）。left 每天只和昨天比：security[i] ≤ security[i-1]，跌势没断，left[i]=left[i-1]+1；涨了就断，left[i] 归 0。整段的保证在接力里——left[i-1] 已担保前面每对都不涨，今天只补验最新一对。right 反向同理，和后一天比。不等号带等于：持平不断段。

[5,3,3,3,5,6,2]上left、right各长什么样

先填 left：第 0 天左边没人，left[0]=0；3 ≤ 5，left[1]=1；3 ≤ 3，left[2]=2；3 ≤ 3，left[3]=3；5 > 3 断，left[4]=0；6 > 5 断，left[5]=0；2 ≤ 6，left[6]=1。调头填 right：right[6]=0；6 > 2，right[5]=0；5 ≤ 6，right[4]=1；3 ≤ 5，right[3]=2；3 ≤ 3，right[2]=3；3 ≤ 3，right[1]=4；5 > 3，right[0]=0。

逐天取小：第 2 天 min(2,3)=2、第 3 天 min(3,2)=2，都够 2，收；第 4 天 min(0,1)=0，不够；其余日子 left 或 right 为 0。答案正是题面给的 [2,3]。

把 ≤ 写成 <，第 2、3 天为什么双双消失

把 ≤ 抄成 <，两对 3 和 3 立刻成了断点，left[2]、left[3] 归 0，第 2、3 天双双出局，答案变成空数组。time=0 时 0 ≤ min 恒成立，所有下标都收，题面例子 [1,1,1,1,1] 输出 [0,1,2,3,4]。n ≤ 2×time 时哪天都凑不齐左右两肩，代码开头直接返回空。三趟线性扫描，时间 O(n)；两张长度 n 的表，空间 O(n)。

Python

from __future__ import annotations
from typing import *
from collections import *
from functools import *
from itertools import *
from math import *
from heapq import *
from bisect import *
class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        if n <= time * 2:
            return []
        left, right = [0] * n, [0] * n
        for i in range(1, n):
            if security[i] <= security[i - 1]:
                left[i] = left[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if security[i] <= security[i + 1]:
                right[i] = right[i + 1] + 1
        return [i for i in range(n) if time <= min(left[i], right[i])]

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> goodDaysToRobBank(vector<int>& security, int time) {
        int n = security.size();
        if (n <= time * 2) return {};
        vector<int> left(n);
        vector<int> right(n);
        for (int i = 1; i < n; ++i)
            if (security[i] <= security[i - 1])
                left[i] = left[i - 1] + 1;
        for (int i = n - 2; i >= 0; --i)
            if (security[i] <= security[i + 1])
                right[i] = right[i + 1] + 1;
        vector<int> ans;
        for (int i = time; i < n - time; ++i)
            if (time <= min(left[i], right[i]))
                ans.push_back(i);
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public List<Integer> goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        if (n <= time * 2) {
            return Collections.emptyList();
        }
        int[] left = new int[n];
        int[] right = new int[n];
        for (int i = 1; i < n; ++i) {
            if (security[i] <= security[i - 1]) {
                left[i] = left[i - 1] + 1;
            }
        }
        for (int i = n - 2; i >= 0; --i) {
            if (security[i] <= security[i + 1]) {
                right[i] = right[i + 1] + 1;
            }
        }
        List<Integer> ans = new ArrayList<>();
        for (int i = time; i < n - time; ++i) {
            if (time <= Math.min(left[i], right[i])) {
                ans.add(i);
            }
        }
        return ans;
    }
}