Description
You and a gang of thieves are planning on robbing a bank. You are given a 0-indexed integer array security, where security[i] is the number of guards on duty on the ith day. The days are numbered starting from 0. You are also given an integer time.
The ith day is a good day to rob the bank if:
- There are at least
time days before and after the ith day,
- The number of guards at the bank for the
time days before i are non-increasing, and
- The number of guards at the bank for the
time days after i are non-decreasing.
More formally, this means day i is a good day to rob the bank if and only if security[i - time] >= security[i - time + 1] >= ... >= security[i] <= ... <= security[i + time - 1] <= security[i + time].
Return a list of all days (0-indexed) that are good days to rob the bank. The order that the days are returned in does not matter.
Example 1:
Input: security = [5,3,3,3,5,6,2], time = 2
Output: [2,3]
Explanation:
On day 2, we have security[0] >= security[1] >= security[2] <= security[3] <= security[4].
On day 3, we have security[1] >= security[2] >= security[3] <= security[4] <= security[5].
No other days satisfy this condition, so days 2 and 3 are the only good days to rob the bank.
Example 2:
Input: security = [1,1,1,1,1], time = 0
Output: [0,1,2,3,4]
Explanation:
Since time equals 0, every day is a good day to rob the bank, so return every day.
Example 3:
Input: security = [1,2,3,4,5,6], time = 2
Output: []
Explanation:
No day has 2 days before it that have a non-increasing number of guards.
Thus, no day is a good day to rob the bank, so return an empty list.
Constraints:
1 <= security.length <= 1050 <= security[i], time <= 105
Solutions
Solution 1
PythonJavaC++GoTypeScriptRust
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])](code-box)
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;
}
}(code-box)
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;
}
};(code-box)
func goodDaysToRobBank(security []int, time int) []int {
n := len(security)
if n <= time*2 {
return []int{}
}
left := make([]int, n)
right := make([]int, n)
for i := 1; i < n; i++ {
if security[i] <= security[i-1] {
left[i] = left[i-1] + 1
}
}
for i := n - 2; i >= 0; i-- {
if security[i] <= security[i+1] {
right[i] = right[i+1] + 1
}
}
var ans []int
for i := time; i < n-time; i++ {
if time <= left[i] && time <= right[i] {
ans = append(ans, i)
}
}
return ans
}(code-box)
function goodDaysToRobBank(security: number[], time: number): number[] {
const n = security.length;
if (n <= time * 2) {
return [];
}
const l = new Array(n).fill(0);
const r = new Array(n).fill(0);
for (let i = 1; i < n; i++) {
if (security[i] <= security[i - 1]) {
l[i] = l[i - 1] + 1;
}
if (security[n - i - 1] <= security[n - i]) {
r[n - i - 1] = r[n - i] + 1;
}
}
const res = [];
for (let i = time; i < n - time; i++) {
if (time <= Math.min(l[i], r[i])) {
res.push(i);
}
}
return res;
}(code-box)
use std::cmp::Ordering;
impl Solution {
pub fn good_days_to_rob_bank(security: Vec<i32>, time: i32) -> Vec<i32> {
let time = time as usize;
let n = security.len();
if time * 2 >= n {
return vec![];
}
let mut g = vec![0; n];
for i in 1..n {
g[i] = match security[i].cmp(&security[i - 1]) {
Ordering::Less => -1,
Ordering::Greater => 1,
Ordering::Equal => 0,
};
}
let (mut a, mut b) = (vec![0; n + 1], vec![0; n + 1]);
for i in 1..=n {
a[i] = a[i - 1] + (if g[i - 1] == 1 { 1 } else { 0 });
b[i] = b[i - 1] + (if g[i - 1] == -1 { 1 } else { 0 });
}
let mut res = vec![];
for i in time..n - time {
if a[i + 1] - a[i + 1 - time] == 0 && b[i + 1 + time] - b[i + 1] == 0 {
res.push(i as i32);
}
}
res
}
}(code-box)
