#2100

Find Good Days to Rob the Bank

specialist · 850 · lc medium +31 · verified · 51.4% accepted · 1,000 likes · top 40%

⚑ Running Min/Max Tracking

Description

You and a gang of thieves are planning to rob 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.

Day i is considered a good day to rob the bank when all of the following hold:

 - There are at least time days both before and after day i,

 - The guard counts for the time days preceding day i are non-increasing, and

 - The guard counts for the time days following day i are non-decreasing.

Formally, day i is good 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 good days (0-indexed). The order in which the days are returned 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.

Code

1
2
3