LeetCode 题解工作台
适合野炊的日子
你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security ，其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。 如果第 i 天满足以下所有条件，我们称它为一个适合野炊的日子： 第 i 天前和后都分别至少有 time 天。 …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
class Solution: def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
你和朋友们准备去野炊。给你一个下标从 0 开始的整数数组 security ，其中 security[i] 是第 i 天的建议出行指数。日子从 0 开始编号。同时给你一个整数 time 。
如果第 i 天满足以下所有条件，我们称它为一个适合野炊的日子：
- 第
i天前和后都分别至少有time天。 - 第
i天前连续time天建议出行指数都是非递增的。 - 第
i天后连续time天建议出行指数都是非递减的。
更正式的，第 i 天是一个适合野炊的日子当且仅当：security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].
请你返回一个数组，包含 所有 适合野炊的日子（下标从 0 开始）。返回的日子可以 任意 顺序排列。
示例 1：
输入：security = [5,3,3,3,5,6,2], time = 2 输出：[2,3] 解释： 第 2 天，我们有 security[0] >= security[1] >= security[2] <= security[3] <= security[4] 。 第 3 天，我们有 security[1] >= security[2] >= security[3] <= security[4] <= security[5] 。 没有其他日子符合这个条件，所以日子 2 和 3 是适合野炊的日子。
示例 2：
输入：security = [1,1,1,1,1], time = 0 输出：[0,1,2,3,4] 解释： 因为 time 等于 0 ，所以每一天都是适合野炊的日子，所以返回每一天。
示例 3：
输入：security = [1,2,3,4,5,6], time = 2 输出：[] 解释： 没有任何一天的前 2 天建议出行指数是非递增的。 所以没有适合野炊的日子，返回空数组。
提示：
1 <= security.length <= 1050 <= security[i], time <= 105
解题思路
方法一
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])]
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Look for an understanding of dynamic programming and how to optimize brute force solutions.
- question_mark
Check if the candidate can think of ways to minimize redundant operations.
- question_mark
Evaluate how well the candidate understands prefix sums and state transitions for optimization.
常见陷阱
外企场景- error
Failing to recognize the overlap between different days, leading to redundant operations.
- error
Not optimizing the solution beyond brute force, resulting in excessive time complexity.
- error
Missing the use of dynamic programming or prefix sums to reduce the number of checks required.
进阶变体
外企场景- arrow_right_alt
What if `time` equals 0? In this case, every day is a good day, and the solution needs to handle that scenario.
- arrow_right_alt
How would the approach change if the array is reversed? The same principles apply, but adjustments in the direction of the transitions are needed.
- arrow_right_alt
If there were additional constraints on the number of guards or days, the solution might need further optimization or adjustments in the approach.