题目描述
思路解析动画文字版
最直接的笨办法是把每天都当候选,往左数 time 天看是否一路非递增、往右数 time 天看是否一路非递减,可这样相邻两天要比的那批趋势几乎重叠,同一对相邻关系被反复看。与其反复数,不如一次性预处理成两个数:左边非递增攒成 left,右边非递减攒成 right,谁短算谁,够 time 就是好日子。下面先做第一遍,把 left 一格一格算出来。
这是 7 天的出行指数,下标 0 到 6。要找的好日子像谷底:左肩一路往下走(非递增)、右肩一路往上走(非递减),而且两边各要够 2 天。接下来分两遍处理,先量左肩,再量右肩。
第一遍从左往右量左肩。第 0 天左边没有别的天,非递增段长度是 0,所以 left[0]=0。从第 1 天开始,每天只看它和前一天:今天的指数只要不高于昨天,非递增就延续。
看第 1 天,指数 3,和前一天 5 比,3 不高于 5,非递增接着往下,left[1]=left[0]+1=1。绿色这一段就是到第 1 天为止的连续非递增段,共 1 步。
看第 2 天,指数 3,和前一天 3 比,3 不高于 3,非递增接着往下,left[2]=left[1]+1=2。绿色这一段就是到第 2 天为止的连续非递增段,共 2 步。
看第 3 天,指数 3,和前一天 3 比,3 不高于 3,非递增接着往下,left[3]=left[2]+1=3。绿色这一段就是到第 3 天为止的连续非递增段,共 3 步。
看第 4 天,指数 5,和前一天 3 比,5 反而更大,非递增在这里断了。left[4] 归 0,第 4 天自己重新起头,标红提示这里是个断点。
看第 5 天,指数 6,和前一天 5 比,6 反而更大,非递增在这里断了。left[5] 归 0,第 5 天自己重新起头,标红提示这里是个断点。
看第 6 天,指数 2,和前一天 6 比,2 不高于 6,非递增接着往下,left[6]=left[5]+1=1。绿色这一段就是到第 6 天为止的连续非递增段,共 1 步。
第一遍走完,left=[0,1,2,3,0,0,1]。这排数字的意思是:第 3 天往左能连着 3 天非递增(5≥3≥3≥3),所以 left[3]=3;第 4 天指数反弹到 5,left[4] 归 0。left 越大,说明左肩下坡越长。左肩量好了,换右肩。
第二遍从右往左量右肩,方向反过来。最后一天第 6 天右边没有别的天,right[6]=0。往左每天只看它和后一天:今天不高于后一天,非递减就延续。
看第 5 天,指数 6,和后一天 2 比,6 反而更大,往右非递减断了。right[5] 归 0,标红提示这是右肩的断点。
看第 4 天,指数 5,和后一天 6 比,5 不高于 6,往右非递减接着上,right[4]=right[5]+1=1。绿色这一段是从第 4 天起的连续非递减段,共 1 步。
看第 3 天,指数 3,和后一天 5 比,3 不高于 5,往右非递减接着上,right[3]=right[4]+1=2。绿色这一段是从第 3 天起的连续非递减段,共 2 步。
看第 2 天,指数 3,和后一天 3 比,3 不高于 3,往右非递减接着上,right[2]=right[3]+1=3。绿色这一段是从第 2 天起的连续非递减段,共 3 步。
看第 1 天,指数 3,和后一天 3 比,3 不高于 3,往右非递减接着上,right[1]=right[2]+1=4。绿色这一段是从第 1 天起的连续非递减段,共 4 步。
看第 0 天,指数 5,和后一天 3 比,5 反而更大,往右非递减断了。right[0] 归 0,标红提示这是右肩的断点。
第二遍走完,right=[0,4,3,2,1,0,0]。比如第 1 天往右能连着 4 步非递减(3≤3≤3≤5≤6),right[1]=4;第 5 天指数 6 之后掉到 2,right[5] 归 0。两把尺子都备齐了,接下来逐天裁决。
开始裁决。一天要合格,左肩和右肩都得够 2 天,也就是 min(left[i], right[i]) 至少是 2。灰掉的第 0、1、5、6 天靠边站:它们离数组两端太近,一边根本凑不够 2 天。真正要逐个看的是中间的第 2、3、4 天。
第 2 天,左肩 left=2、右肩 right=3,取小的是 2,达到了 time=2。这一天左边有 2 天非递增、右边有 2 天非递减,正是一个谷底。底色框出它前后各 2 天的范围,把第 2 天收进答案。
第 3 天,左肩 left=3、右肩 right=2,取小的是 2,达到了 time=2。这一天左边有 2 天非递增、右边有 2 天非递减,正是一个谷底。底色框出它前后各 2 天的范围,把第 3 天收进答案。
第 4 天,左肩 left=0、右肩 right=1,取小的是 0,还不到 time=2。它左边非递增不够 2 天,谷底不成立,标红跳过。
全部裁决完。绿色的第 2 天和第 3 天,left 和 right 都够 2,是货真价实的谷底;其余日子灰掉。答案就是 [2, 3],跟开头说的对上了。判定始终只看一条:min(left[i], right[i]) 是不是够 time。
边界想清:time=0 全收、全程上升为空、n ≤ time 乘 2 直接为空。
面试重点:两遍前缀把「前非递增后非递减」拆成 left 与 right,min 达标即好日子,时间 O(n)。
参考代码
from __future__ import annotationsfrom 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])]复杂度
- 时间：O(n)，n 是天数。第一遍扫一遍算 left,第二遍扫一遍算 right,收集答案再扫一遍,三趟都是线性,每格常数操作,合起来仍是 O(n)
- 空间：O(n)，按峰值算。额外开了 left 和 right 两个长度 n 的数组,峰值占用随 n 线性增长。若允许把结果数组算进输出、只看辅助结构,主要就是这两个前缀数组
易错点
面试追问把动画讲成自己的话
追问这题的核心思路一句话怎么说?
追问不用两个数组,能省空间吗?
追问为什么时间能做到线性?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
股票平滑下跌阶段的数目
LeetCode 2110 · 中等 · 沿着 动态规划套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题