LeetCode 2100 适合打劫银行的日子（Find Good Days to Rob the Bank）：前缀/后缀预处理与单调性判定

LeetCode 2100 适合打劫银行的日子（Find Good Days to Rob the Bank）：前缀/后缀预处理与单调性判定

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode

本篇技术指南围绕 LeetCode 5935（力扣题目编号 2100）「适合打劫银行的日子」展开，基于本仓库 problems/5935.find-good-days-to-rob-the-bank.md 题解文档，从题目语义、双方向单调性预处理、线性扫描判定三个层面完整还原解题思路，并结合仓库动态规划主题章节 thinkings/dynamic-programming.md 中的滚动数组与状态设计思想给出源码级扩展。读者学完后将掌握一类"连续单调区间快速判定"问题的标准解法：用两个预处理数组分别记录左侧连续非递增长度与右侧连续非递减长度，在 O(n) 时间内求解，并能把该套路迁移到类似的数组区间条件判定题目中。

题目概述

题目描述

你和一群强盗准备打劫银行。给你一个下标从 0 开始的整数数组security，其中security[i]是第 i 天执勤警卫的数量，日子从 0 开始编号。同时给你一个整数time。

如果第 i 天满足以下所有条件，我们称它为一个适合打劫银行的日子：

1. 第 i 天前和后都分别至少有time天；
2. 第 i 天前连续time天警卫数目都是非递增的；
3. 第 i 天后连续time天警卫数目都是非递减的。

更形式化地，第 i 天是一个适合打劫银行的日子当且仅当：

security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time]

请你返回一个数组，包含所有适合打劫银行的日子（下标从 0 开始），返回的日子可以任意顺序排列。

该题在力扣中的题号为2100，在仓库 README.md 与 SUMMARY.md 中均以「2100. 适合打劫银行的日子」收录，文档文件命名为5935.find-good-days-to-rob-the-bank.md，对应仓库内部约定：文件名前缀使用力扣接口题号，题目本身以find-good-days-to-rob-the-bank标识。

条件语义拆解

题目的核心条件是围绕某一个位置 i 的"V 字形"单调性：

• 左侧：从i - time到i，警卫数量必须非递增（即向左看，越靠近 i 数量越大或相等，形成一段"逐渐变大或持平"的序列）；
• 右侧：从i到i + time，警卫数量必须非递减（即向右看，越远离 i 数量越大或相等，形成一段"逐渐变小或持平"的序列）。

注意"非递增"和"非递减"都包含相等的情况（>=与<=），这与严格递增/严格递减不同，是本题容易忽略的边界点。

示例与边界情况

原文档提供了四个覆盖典型场景的示例，这里逐一展开说明，并标注其中蕴含的边界条件：

示例 1

输入：security = [5,3,3,3,5,6,2], time = 2 输出：[2,3]

• 第 2 天（值 3）：security[0] >= security[1] >= security[2] <= security[3] <= security[4]，即5 >= 3 >= 3 <= 3 <= 5成立；
• 第 3 天（值 3）：security[1] >= security[2] >= security[3] <= security[4] <= security[5]，即3 >= 3 >= 3 <= 5 <= 6成立；
• 其余位置不满足，因此输出[2,3]。

该示例展示了连续相等值（[3,3,3]）可以同时充当多个合法日子的"谷底"，因为非递增/非递减允许相等。

示例 2

输入：security = [1,1,1,1,1], time = 0 输出：[0,1,2,3,4]

当time = 0时，"前和后分别至少有 time 天"这一条件自动满足，左右两侧各需要考察 0 天，即每一天都是合法日子。这是对"至少 time 天"边界的直接考验：位置 i 必须满足i >= time且n - 1 - i >= time，当time = 0时任何位置都满足。

示例 3

输入：security = [1,2,3,4,5,6], time = 2 输出：[]

数组整体严格递增，任意位置左侧都不存在连续 2 天非递增的序列，因此没有合法日子，返回空数组。此例说明左侧单调性一旦不满足，即使右侧再符合也无济于事。

示例 4

输入：security = [1], time = 5 输出：[]

数组长度只有 1，而time = 5，任何位置都无法满足"前和后分别至少有 5 天"的前置条件，返回空数组。此例说明边界条件优先于单调性判断：即使单调性满足，只要窗口长度不足，就应直接排除。

数据范围与提示

1 <= security.length <= 10^5 0 <= security[i], time <= 10^5

• security长度最大可达 10 万，因此任何 O(n^2) 的朴素做法（对每个位置向两侧扩展检查 time 天）在最坏情况下都会超时，必须设计 O(n) 级别的算法；
• time可以为 0，也可以大于数组长度（如示例 4），需要在前置条件中处理；
• security[i]非负，取值本身不参与复杂运算，只需比较大小关系。

前置知识

原文档将本题的前置知识标注为动态规划。需要说明的是，本题严格意义上属于"动态规划思想的应用"——它并不需要求解最优值，而是利用与 DP 相同的状态递推与查表思路：

1. 将"位置 i 左侧连续非递增的长度"视为一个可递推的状态；
2. 该状态可由前一个位置i-1的状态在 O(1) 时间内转移得到；
3. 预处理完成后，通过查表（l[i]、r[i]）在 O(1) 时间内完成对每个位置的判定。

这与仓库 thinkings/dynamic-programming.md 中对动态规划"将一件事情分成若干阶段，通过阶段之间的转移达到目标"的概括一致：本题的阶段就是数组下标，转移就是相邻元素之间的大小关系判断，最终目标是确定每个位置是否满足条件。

核心思路：双向预处理 + 线性扫描

思路推导

对于每一个位置 i，我们如何判断其是否适合打劫？显然需要知道两件事：

1. i前面有多少个连续位置满足"小于等于当前位置"（即从 i 向左看，序列非递增，或者说security[j] >= security[j+1]连续成立的长度）；
2. i后面有多少个连续位置满足"大于等于当前位置"（即从 i 向右看，序列非递减，或者说security[j] <= security[j+1]连续成立的长度）。

因此我们可以先进行一次预处理，将上面的两个信息求出来。不妨使用两个数组l和r分别存储：

• l[i]表示 i 左侧有多少个连续位置是小于等于security[i]的（即向左连续满足security[j-1] >= security[j]的步数）；
• r[i]表示 i 右侧有多少个连续位置是大于等于security[i]的（即向右连续满足security[j] <= security[j+1]的步数）。

接下来只需要遍历一次security，判断每个位置是否满足l[i] >= time且r[i] >= time，如果满足就将其下标加入结果数组ans。

关键点

• 预处理出数组l和r，将每个位置两侧的连续单调长度在 O(n) 内求出；
• 两次独立的方向遍历：l从左向右递推，r从右向左递推；
• 最终判定是 O(1) 查表：l[i] >= time and r[i] >= time，不需要再向两侧扩展比较。

正确性论证

1. 递推的单调性保持：若security[i] <= security[i-1]，则 i 左侧的连续非递增长度等于i-1左侧的连续非递增长度加 1（把 i 自己接在 i-1 的序列后面）；若不等，则说明以 i 为右端点的连续非递增段长度为 0。这正是"当前状态只和前一个状态有关"的 DP 式转移，与 thinkings/dynamic-programming.md 中"当前状态只和前两个状态有关，因此只需要存储这两个"的滚动数组思想同源——只不过本题需要同时保留所有位置的状态，因此采用完整数组而非滚动变量。

2. 判定的充分必要性：l[i] >= time意味着从 i 向左至少存在连续 time+1 个位置（含 i）满足非递增，等价于security[i-time] >= ... >= security[i]；r[i] >= time同理等价于security[i] <= ... <= security[i+time]。两者同时成立恰好对应题目形式化条件。同时前置条件"第 i 天前和后分别至少有 time 天"也由l[i] >= time（要求 i 至少有 time 个左侧邻居，隐含i >= time）与r[i] >= time（隐含n-1-i >= time）自动保证——因为当左侧可连续非递增的步数达到 time 时，i 前面必然至少有 time 天。

代码实现

原文档提供 Python3 实现，这里完整保留并补充注释：

class Solution: def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]: n = len(security) # l[i]：i 左侧连续满足非递增（security[j-1] >= security[j]）的步数 # r[i]：i 右侧连续满足非递减（security[j] <= security[j+1]）的步数 l, r = [0] * n, [0] * n ans = [] # 从左向右递推 l：security[i] <= security[i-1] 时左侧非递增段延续 for i in range(1, n): if security[i] <= security[i-1]: l[i] += l[i-1] + 1 # 从右向左递推 r：security[i] <= security[i+1] 时右侧非递减段延续 for i in range(n - 2, -1, -1): if security[i] <= security[i+1]: r[i] += r[i+1] + 1 # 查表判定：两侧连续单调长度均达到 time 即为合法日子 for i in range(n): if l[i] >= time and r[i] >= time: ans.append(i) return ans

代码逐段解读

1. 初始化：l、r均初始化为全 0 的 n 长度数组。数组默认值为 0 是正确的基础态——当某个位置不满足延续条件时，其对应侧连续长度为 0。

2. 正向递推 l：for i in range(1, n)中，若security[i] <= security[i-1]，则l[i] = l[i-1] + 1（原代码以+=形式书写，等价于直接赋值，因为l[i]初始为 0）。注意l[i]表示的是"步数"而非"包含自身的个数"：l[0] = 0，若整个数组非递增，则l[n-1] = n-1。

3. 反向递推 r：for i in range(n-2, -1, -1)从右向左扫描，若security[i] <= security[i+1]，则r[i] = r[i+1] + 1。同理r[n-1] = 0。

4. 查表判定：单次循环中同时检查l[i] >= time与r[i] >= time，满足则ans.append(i)。结果顺序自然为下标升序，也满足题目"可以任意顺序排列"的要求。

边界情况验证

• time = 0（示例 2）：任何位置的l[i] >= 0、r[i] >= 0恒成立，因此全部下标都被加入答案，输出[0,1,2,3,4]；
• n = 1, time = 5（示例 4）：两个递推循环体均不执行，l[0] = r[0] = 0 < 5，答案为空数组；
• 严格递增数组（示例 3）：正向递推中security[i] <= security[i-1]恒不成立，l全为 0，任何time > 0都无法满足l[i] >= time，答案为空。

复杂度分析

令 n 为数组长度。

• 时间复杂度：O(n)。三次线性扫描（两次预处理递推 + 一次查表判定），总操作次数约为 3n，与 n 呈线性关系；
• 空间复杂度：O(n)。需要两个长度为 n 的辅助数组l和r，用于存储每个位置两侧的单调长度。

对于n <= 10^5的数据规模，O(n) 的时间与空间均处于安全范围。

深度扩展：从本题看"单调性预处理"套路

与其他题解方法的关联

本仓库中还有多道题目采用了"预处理 + 查表"或"方向递推"的同类思想，可以作为本题的延伸阅读：

• 42. 接雨水：同样使用"从左到右"与"从右到左"两个方向的预处理数组（leftMax/rightMax），再对每个位置做 O(1) 判定，与本题的双向数组结构高度一致；
• 84. 柱状图中最大的矩形：利用单调栈快速求出每个柱子左右两侧"第一个比它矮"的位置，同样是"为每个位置求出两侧信息"的思路变体；
• 1186. 删除一次得到子数组最大和：也出现了l、r双数组 + 双向递推的代码结构，用于分别记录前缀与后缀信息。

这三道题与本题共同构成了一类可迁移的解题模式：当判定条件涉及"每个位置左右两侧的连续区间性质"时，先通过两次方向相反的线性递推把两侧信息存入数组，再统一扫描判定。

从动态规划视角看状态设计

结合仓库 thinkings/dynamic-programming.md 的内容，可以从更抽象的层面审视本题：

• 状态定义：l[i]/r[i]是典型的"以位置 i 为端点"的状态，状态总数恰为 n；
• 状态转移：l[i] = (security[i] <= security[i-1]) ? l[i-1] + 1 : 0，转移只依赖前一个状态，是"无后效性"的体现——判定 i 时不需要知道 i 之后的信息（l）或 i 之前的信息（r）；
• 与滚动数组的对比：动态规划中"当前状态只和前一个状态有关"时通常可以用滚动数组把空间压到 O(1)（如 thinkings/dynamic-programming.md 中爬楼梯一例）。本题之所以保留完整数组，是因为每个位置的状态都要在最后阶段独立查表，无法被覆盖丢弃，这说明了"状态是否需要被后续多次复用"是决定能否滚动优化的关键判据；
• 记忆化递归 vs 迭代：该主题文档指出记忆化递归无法使用滚动数组优化，而迭代式 dp table 可以。本题的迭代双向递推正属于后者，天然具备构造辅助数组的便利性。

可能的变式与进一步思考

• 严格单调版本：若把"非递增/非递减"改为"严格递减/严格递增"，只需把比较符<=改为<，其余结构不变；
• 左右窗口长度不同：若左侧要求 time1、右侧要求 time2，只需把判定条件改为l[i] >= time1 and r[i] >= time2；
• 空间优化：r数组可以先求出来，然后从右向左扫描时用滚动变量携带"右侧连续长度"，在扫描过程中直接判定并生成答案，从而只保留l一个数组，空间可优化为只依赖单个 O(n) 数组（时间仍为 O(n)）。由于本题判定条件同时依赖两侧信息，l数组仍需完整保留，因此最坏空间仍为 O(n)；
• 二维/多维度推广：该思路可推广到"二维网格中每个格子向上/向下连续满足条件的长度"等场景，是很多矩阵类 DP 题目的前置步骤。

小结

本题表面是"打劫银行"的场景包装，实质考查的是连续区间单调性的快速判定能力。标准解法分为三步：

1. 从左向右递推l[i]，记录位置 i 左侧连续非递增的长度；
2. 从右向左递推r[i]，记录位置 i 右侧连续非递减的长度；
3. 单次扫描判定l[i] >= time and r[i] >= time，收集答案。

该解法的时间复杂度为 O(n)、空间复杂度为 O(n)，完全适配n <= 10^5的数据范围，同时天然覆盖time = 0、数组过短、整体单调等多种边界情况。本仓库题解原文位于 problems/5935.find-good-days-to-rob-the-bank.md，完整题目列表见 README.md（对应条目「2100. 适合打劫银行的日子」）。掌握"双向预处理 + 查表判定"这一套路后，可以轻松迁移到接雨水、柱状图等同类区间单调性问题中。

【免费下载链接】leetcodeLeetCode Solutions: A Record of My Problem Solving Journey.( leetcode题解，记录自己的leetcode解题之路。)项目地址: https://gitcode.com/gh_mirrors/le/leetcode