适合野炊的日子 图解题解
这道题到底在问什么
- 输入
- security=[5,3,3,3,5,6,2], time=2
- 输出
- [2,3]
- 输入
- security=[1,1,1,1,1], time=0
- 输出
- [0,1,2,3,4]
先想最直接的笨办法
最直接的笨办法是把每天都当候选,往左数 time 天看是否一路非递增、往右数 time 天看是否一路非递减,可这样相邻两天要比的那批趋势几乎重叠,同一对相邻关系被反复看。与其反复数,不如一次性预处理成两个数:左边非递增攒成 left,右边非递减攒成 right,谁短算谁,够 time 就是好日子。下面先做第一遍,把 left 一格一格算出来。（动画第 3 步）
最优解：一步一步想明白
- 3最直接的笨办法是把每天都当候选,往左数 time 天看是否一路非递增、往右数 time 天看是否一路非递减,可这样相邻两天要比的那批趋势几乎重叠,同一对相邻关系被反复看。与其反复数,不如一次性预处理成两个数:左边非递增攒成 left,右边非递减攒成 right,谁短算谁,够 time 就是好日子。下面先做第一遍,把 left 一格一格算出来。
- 4这是 7 天的出行指数,下标 0 到 6。要找的好日子像谷底:左肩一路往下走(非递增)、右肩一路往上走(非递减),而且两边各要够 2 天。接下来分两遍处理,先量左肩,再量右肩。
- 5第一遍从左往右量左肩。第 0 天左边没有别的天,非递增段长度是 0,所以 left[0]=0。从第 1 天开始,每天只看它和前一天:今天的指数只要不高于昨天,非递增就延续。
- 6看第 1 天,指数 3,和前一天 5 比,3 不高于 5,非递增接着往下,left[1]=left[0]+1=1。绿色这一段就是到第 1 天为止的连续非递增段,共 1 步。
- 7看第 2 天,指数 3,和前一天 3 比,3 不高于 3,非递增接着往下,left[2]=left[1]+1=2。绿色这一段就是到第 2 天为止的连续非递增段,共 2 步。
- 8看第 3 天,指数 3,和前一天 3 比,3 不高于 3,非递增接着往下,left[3]=left[2]+1=3。绿色这一段就是到第 3 天为止的连续非递增段,共 3 步。
- 9看第 4 天,指数 5,和前一天 3 比,5 反而更大,非递增在这里断了。left[4] 归 0,第 4 天自己重新起头,标红提示这里是个断点。
- 10看第 5 天,指数 6,和前一天 5 比,6 反而更大,非递增在这里断了。left[5] 归 0,第 5 天自己重新起头,标红提示这里是个断点。
- 11看第 6 天,指数 2,和前一天 6 比,2 不高于 6,非递增接着往下,left[6]=left[5]+1=1。绿色这一段就是到第 6 天为止的连续非递增段,共 1 步。
- 12第一遍走完,left=[0,1,2,3,0,0,1]。这排数字的意思是:第 3 天往左能连着 3 天非递增(5≥3≥3≥3),所以 left[3]=3;第 4 天指数反弹到 5,left[4] 归 0。left 越大,说明左肩下坡越长。左肩量好了,换右肩。
- 13第二遍从右往左量右肩,方向反过来。最后一天第 6 天右边没有别的天,right[6]=0。往左每天只看它和后一天:今天不高于后一天,非递减就延续。
- 14看第 5 天,指数 6,和后一天 2 比,6 反而更大,往右非递减断了。right[5] 归 0,标红提示这是右肩的断点。
- 15看第 4 天,指数 5,和后一天 6 比,5 不高于 6,往右非递减接着上,right[4]=right[5]+1=1。绿色这一段是从第 4 天起的连续非递减段,共 1 步。
- 16看第 3 天,指数 3,和后一天 5 比,3 不高于 5,往右非递减接着上,right[3]=right[4]+1=2。绿色这一段是从第 3 天起的连续非递减段,共 2 步。
- 17看第 2 天,指数 3,和后一天 3 比,3 不高于 3,往右非递减接着上,right[2]=right[3]+1=3。绿色这一段是从第 2 天起的连续非递减段,共 3 步。
- 18看第 1 天,指数 3,和后一天 3 比,3 不高于 3,往右非递减接着上,right[1]=right[2]+1=4。绿色这一段是从第 1 天起的连续非递减段,共 4 步。
- 19看第 0 天,指数 5,和后一天 3 比,5 反而更大,往右非递减断了。right[0] 归 0,标红提示这是右肩的断点。
- 20第二遍走完,right=[0,4,3,2,1,0,0]。比如第 1 天往右能连着 4 步非递减(3≤3≤3≤5≤6),right[1]=4;第 5 天指数 6 之后掉到 2,right[5] 归 0。两把尺子都备齐了,接下来逐天裁决。
- 21开始裁决。一天要合格,左肩和右肩都得够 2 天,也就是 min(left[i], right[i]) 至少是 2。灰掉的第 0、1、5、6 天靠边站:它们离数组两端太近,一边根本凑不够 2 天。真正要逐个看的是中间的第 2、3、4 天。
- 22第 2 天,左肩 left=2、右肩 right=3,取小的是 2,达到了 time=2。这一天左边有 2 天非递增、右边有 2 天非递减,正是一个谷底。底色框出它前后各 2 天的范围,把第 2 天收进答案。
- 23第 3 天,左肩 left=3、右肩 right=2,取小的是 2,达到了 time=2。这一天左边有 2 天非递增、右边有 2 天非递减,正是一个谷底。底色框出它前后各 2 天的范围,把第 3 天收进答案。
- 24第 4 天,左肩 left=0、右肩 right=1,取小的是 0,还不到 time=2。它左边非递增不够 2 天,谷底不成立,标红跳过。
- 25全部裁决完。绿色的第 2 天和第 3 天,left 和 right 都够 2,是货真价实的谷底;其余日子灰掉。答案就是 [2, 3],跟开头说的对上了。判定始终只看一条:min(left[i], right[i]) 是不是够 time。
⚠️ 容易写错的地方
✗ 错：把左右两边的方向记反
✓ 对：左边要非递增(往下),右边要非递减(往上)
好日子是谷底,左肩下坡、右肩上坡;方向反了会把山峰当谷底,全错
✗ 错：用严格大于或严格小于判断
✓ 对：两边都用 ≤ 这类允许相等的比较
题面用的是 ≥ 和 ≤,相等的两天(如 3,3,3)仍算非递增或非递减,用严格号会把持平错判成断开
✗ 错：忘了两端凑不够 time 天的日子
✓ 对：min(left[i], right[i]) ≥ time 天然排除两端
left[i] 够 time 就保证左边有 time 天,right[i] 够 time 保证右边有 time 天,取 min 一并卡住,不必另写边界判断
✗ 错：time=0 时漏掉全部日子
✓ 对：time=0 时 min ≥ 0 恒成立,每天都合格
此时不要求任何非递增非递减,应返回所有下标,别被空数组误导
完整代码（Python / C++ / Java）
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;
}
}复杂度
时间
O(n)
n 是天数。第一遍扫一遍算 left,第二遍扫一遍算 right,收集答案再扫一遍,三趟都是线性,每格常数操作,合起来仍是 O(n)
空间
O(n)
按峰值算。额外开了 left 和 right 两个长度 n 的数组,峰值占用随 n 线性增长。若允许把结果数组算进输出、只看辅助结构,主要就是这两个前缀数组
看不够？换成动画再走一遍
上面的推演每一步都对应一帧动画。点开交互动画版，能一步步看着 适合野炊的日子 的数据怎么变、指针怎么走，还能切 Python / Java / C++ 跟着练。
面试官可能追问
这题的核心思路一句话怎么说?+
把「前面非递增、后面非递减」拆成两个可预处理的前缀量:left[i] 记往左连续非递增的天数,right[i] 记往右连续非递减的天数。两遍线性扫描把它们都算出来,某天合格就等价于 time ≤ min(left[i], right[i])。用空间换时间,避免对每天都往两边暴力数。
不用两个数组,能省空间吗?+
能省一些。常规做法是把两个数组压成一个数组加几个变量,渐进空间仍是 O(n),两数组写起来最清晰。若不把返回的答案数组算进来,还能更进一步:只维护「当前往左非递增天数」和「当前往右非递减天数」两个滑动计数,靠相邻比较边扫边判,辅助空间能压到 O(1)。代价是代码更绕、讲起来更费劲,面试里用两个数组把思路讲透通常更稳妥。
为什么时间能做到线性?+
每个前缀量都满足「当前值只依赖相邻的前一个」,所以一遍扫描就能递推出来,不需要对每天重新往两边数。三趟扫描各 O(n),合起来 O(n);相比对每天暴力往两侧走 time 步的 O(n 乘 time),前缀法把重复比较全省了。
想听吴师兄把这道题讲给你听？
文字版和动画都随便看。开通图解算法年卡，可以听吴师兄声线把 适合野炊的日子 一步步讲透（全站 0 节语音精讲，持续扩充）， 卡住的地方还有 AI 私教小欧就着动画帮你拆到懂。
本平台为独立第三方培训机构，与华为技术有限公司无任何关联；课程的服务内容与权益以购买协议为准，学习效果因个人情况而异。「华为 OD」「华为可信」等仅为对岗位与考试方向的客观描述，相关商标归各自权利人所有。