Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

2100. A good day to rob a bank

A day suitable for robbing a bank, medium

I. Title Description:

The following is an example:

Ii. Analysis of Ideas:

1. What ideas does this question examine? What’s your thinking?

Looking at the description and examples of this problem, we should get the following information

  • If time is equal to 0, then banks can be robbed every day, and the result is given all the indices of the array

  • If time is larger than the entire array, the result must be an empty array, not a good day to rob

  • Security [i-time] >= Security [i-time + 1] >=… >= security[i] <= … <= security[i + time – 1] <= security[i + time]

    According to the condition, we know that no matter which day we choose to rob, we need to meet the time days before the day, and the time days after the day, at the same time, the time days before and after the data requirements, our array length needs to meet this condition to play: 2 * time + 1 is less than or equal to the length of the array

Take [5, 3, 3, 3, 5, 6, 2], time = 2

When we select whether a certain date can be robbed, the data in the array corresponding to the time before the current day and the time after the current day are gradually reduced to the data of the current day

So it’s not hard to understand if we feel a little bit like we did in the last post, and if we can also treat it as a special subarray, for example

We only need to find the interval that meets the corresponding time of the day before and the day after the robbery, and then verify whether the interval meets the requirements in the title: the time before the robbery day, the number decreases (can be equal), and the time after the robbery day, the number increases (can be equal).

2. Try coding

So, based on the diagram and logic above, it’s not hard to write code that looks like this

Looks like there’s no problem, so let’s submit it

After submitting it, we were reported an out-of-time limit

When we look at the specific error cases, we can see that 128 use cases were run, but for some large data, this encoding method is not sufficient for this problem

So, there must be room for improvement, and there must be inefficiencies somewhere

3. Think and explore

[5, 3, 3, 3, 5, 6, 2], time = 2

When selecting the first interval, the date of robbery is in the position with the subscript 2, and the number is 3, so we need to judge whether the date of robbery and the first two digits are decreasing. Similarly, we need to judge whether the date of robbery and the next two digits are increasing. If so, then we get a robbery date

So let’s keep going

When advancing to the next interval, if we still use the above method, using a loop to verify whether to increase or decrease, the result of the above code will appear **. For large data, the time limit is exceeded **

In fact, for the previous interval, we have clearly known the increasing or decreasing relationship between the data before and after the robbery date, so when the interval goes back, we specify the new robbery date

You only need to compare the data on the current robbery day with the data on the previous robbery day, and determine whether the rightmost value of the current range is greater than the rightmost value of the last robbery day range

By making an optimization like this, we can greatly reduce the time of the loop and the time complexity of the loop when multiple robbery days are next to each other

The source code is as follows:

func goodDaysToRobBank(security []int, time int) []int {
	if time >= len(security) || 2*time+1 > len(security) {
		return []int{}}if time == 0 {
		res := []int{}
		for i, _ := range security {
			res = append(res, i)
		}
		return res
	}

	length := len(security)
	res := []int{}
	flag := true
	preloc := 0  // Index of last robbery date
	preLastRight := 0  // The rightmost index of the last robbery date
	for i := time; i <= length- 1-time; i++ {
		if flag { // Use a loop to check if it is a robbery day
			if isOk(security, i, time) {
				res = append(res, i)
				flag = false
				preloc = i
				preLastRight = i + time
				continue}}else {
			if security[i] <= security[preloc] && security[i+time] >= security[preLastRight] { // It can be directly compared with the last robbery day
				flag = false
				res = append(res, i)
				preloc = i
				preLastRight = i + time
			} else {
				flag = true}}}return res

}
// Check if it is a robbery day
func isOk(security []int, loc int, time int) bool {
	for i := loc - time; i < loc; i++ {
		if security[i] < security[i+1] {
			return false}}for i := loc + time; i > loc; i-- {
		if security[i] < security[i- 1] {
			return false}}return true
}
Copy the code

From the above coding and comments, it is not difficult to see that this coding is much more efficient than the previous attempt, reducing many useless loops

Of course, this is only one of the solutions, but if you are interested, you can look at a better solution, such as the official one, which directly introduces two arrays, one to record the current index of the left decrement, one to record the right of the increment, as shown in the following figure

Iv. Summary:

The space complexity is O(n), where n is the length of the corresponding array. The official time complexity is O(n), where n is the length of the corresponding array

Today is here, learning, if there is a deviation, please correct

Welcome to like, follow and favorites

Friends, your support and encouragement, I insist on sharing, improve the quality of the power

All right, that’s it for this time

Technology is open, our mentality, should be more open. Embrace change, live in the sun, and strive to move forward.

I am Nezha, welcome to like, see you next time ~