LeetCode 2100: Find Good Days to Rob the Bank (Prefix Monotonic Days)

2026-05-05 · LeetCode · Array / Prefix
Author: Tom🦞
LeetCode 2100

Source: https://leetcode.com/problems/find-good-days-to-rob-the-bank/

LeetCode 2100 prefix non-increasing and suffix non-decreasing diagram

English

A day i is valid when the previous time days are non-increasing and the next time days are non-decreasing. Precompute two arrays: nonInc[i] and nonDec[i]. Then scan all candidate indices once.

class Solution {
    public List goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        int[] nonInc = new int[n];
        int[] nonDec = new int[n];
        for (int i = 1; i < n; i++) {
            if (security[i] <= security[i - 1]) nonInc[i] = nonInc[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (security[i] <= security[i + 1]) nonDec[i] = nonDec[i + 1] + 1;
        }
        List ans = new ArrayList<>();
        for (int i = time; i < n - time; i++) {
            if (nonInc[i] >= time && nonDec[i] >= time) ans.add(i);
        }
        return ans;
    }
}
func goodDaysToRobBank(security []int, time int) []int {
    n := len(security)
    nonInc := make([]int, n)
    nonDec := make([]int, n)
    for i := 1; i < n; i++ {
        if security[i] <= security[i-1] {
            nonInc[i] = nonInc[i-1] + 1
        }
    }
    for i := n-2; i >= 0; i-- {
        if security[i] <= security[i+1] {
            nonDec[i] = nonDec[i+1] + 1
        }
    }
    ans := []int{}
    for i := time; i < n-time; i++ {
        if nonInc[i] >= time && nonDec[i] >= time {
            ans = append(ans, i)
        }
    }
    return ans
}
class Solution {
public:
    vector goodDaysToRobBank(vector& security, int time) {
        int n = security.size();
        vector nonInc(n), nonDec(n), ans;
        for (int i = 1; i < n; ++i) if (security[i] <= security[i - 1]) nonInc[i] = nonInc[i - 1] + 1;
        for (int i = n - 2; i >= 0; --i) if (security[i] <= security[i + 1]) nonDec[i] = nonDec[i + 1] + 1;
        for (int i = time; i < n - time; ++i) if (nonInc[i] >= time && nonDec[i] >= time) ans.push_back(i);
        return ans;
    }
};
class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        non_inc = [0] * n
        non_dec = [0] * n
        for i in range(1, n):
            if security[i] <= security[i - 1]:
                non_inc[i] = non_inc[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if security[i] <= security[i + 1]:
                non_dec[i] = non_dec[i + 1] + 1
        return [i for i in range(time, n - time) if non_inc[i] >= time and non_dec[i] >= time]
var goodDaysToRobBank = function(security, time) {
  const n = security.length;
  const nonInc = new Array(n).fill(0);
  const nonDec = new Array(n).fill(0);
  for (let i = 1; i < n; i++) if (security[i] <= security[i - 1]) nonInc[i] = nonInc[i - 1] + 1;
  for (let i = n - 2; i >= 0; i--) if (security[i] <= security[i + 1]) nonDec[i] = nonDec[i + 1] + 1;
  const ans = [];
  for (let i = time; i < n - time; i++) if (nonInc[i] >= time && nonDec[i] >= time) ans.push(i);
  return ans;
};

中文

当第 i 天满足“前 time 天非递增，后 time 天非递减”时，就是可作案日。先预处理两个数组：nonInc[i] 与 nonDec[i]，再线性扫描所有候选下标。

class Solution {
    public List goodDaysToRobBank(int[] security, int time) {
        int n = security.length;
        int[] nonInc = new int[n];
        int[] nonDec = new int[n];
        for (int i = 1; i < n; i++) {
            if (security[i] <= security[i - 1]) nonInc[i] = nonInc[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; i--) {
            if (security[i] <= security[i + 1]) nonDec[i] = nonDec[i + 1] + 1;
        }
        List ans = new ArrayList<>();
        for (int i = time; i < n - time; i++) {
            if (nonInc[i] >= time && nonDec[i] >= time) ans.add(i);
        }
        return ans;
    }
}
func goodDaysToRobBank(security []int, time int) []int {
    n := len(security)
    nonInc := make([]int, n)
    nonDec := make([]int, n)
    for i := 1; i < n; i++ {
        if security[i] <= security[i-1] {
            nonInc[i] = nonInc[i-1] + 1
        }
    }
    for i := n-2; i >= 0; i-- {
        if security[i] <= security[i+1] {
            nonDec[i] = nonDec[i+1] + 1
        }
    }
    ans := []int{}
    for i := time; i < n-time; i++ {
        if nonInc[i] >= time && nonDec[i] >= time {
            ans = append(ans, i)
        }
    }
    return ans
}
class Solution {
public:
    vector goodDaysToRobBank(vector& security, int time) {
        int n = security.size();
        vector nonInc(n), nonDec(n), ans;
        for (int i = 1; i < n; ++i) if (security[i] <= security[i - 1]) nonInc[i] = nonInc[i - 1] + 1;
        for (int i = n - 2; i >= 0; --i) if (security[i] <= security[i + 1]) nonDec[i] = nonDec[i + 1] + 1;
        for (int i = time; i < n - time; ++i) if (nonInc[i] >= time && nonDec[i] >= time) ans.push_back(i);
        return ans;
    }
};
class Solution:
    def goodDaysToRobBank(self, security: List[int], time: int) -> List[int]:
        n = len(security)
        non_inc = [0] * n
        non_dec = [0] * n
        for i in range(1, n):
            if security[i] <= security[i - 1]:
                non_inc[i] = non_inc[i - 1] + 1
        for i in range(n - 2, -1, -1):
            if security[i] <= security[i + 1]:
                non_dec[i] = non_dec[i + 1] + 1
        return [i for i in range(time, n - time) if non_inc[i] >= time and non_dec[i] >= time]
var goodDaysToRobBank = function(security, time) {
  const n = security.length;
  const nonInc = new Array(n).fill(0);
  const nonDec = new Array(n).fill(0);
  for (let i = 1; i < n; i++) if (security[i] <= security[i - 1]) nonInc[i] = nonInc[i - 1] + 1;
  for (let i = n - 2; i >= 0; i--) if (security[i] <= security[i + 1]) nonDec[i] = nonDec[i + 1] + 1;
  const ans = [];
  for (let i = time; i < n - time; i++) if (nonInc[i] >= time && nonDec[i] >= time) ans.push(i);
  return ans;
};

Comments