Arrays and searching 0/120

Sliding window · 2 of 2

Monotonic queue

Keep a moving window's maximum and minimum with two deques of indices, so the whole scan takes linear time.

2,030 words · 10 min read

Part 1 of 5 The window's maximum

A window that needs its largest and smallest values

A window's sum, product or count can be corrected when a value leaves: subtract the value from the sum, divide it out of the product, take 1 off the count. A window's maximum cannot be corrected that way. Take the window [10, 1, 2], whose maximum is 10. When the 10 leaves, the new maximum is 2, and knowing the old maximum does not help us find it. We would have to look through everything that is still in the window. The next problem needs both the maximum and the minimum of a window whose two ends move:

You get an array nums and an integer limit. Return the length of the longest nonempty subarray in which every two elements differ by at most limit.

Constraints

  • 1≤1 \le len(nums) ≤105\le 10^5
  • 1≤1 \le nums[i] ≤109\le 10^9
  • 0≤0 \le limit ≤109\le 10^9

Sample 1 · Input

nums = [8,2,4,7], limit = 4

Output

2

Sample 2 · Input

nums = [10,1,2,4,7,2], limit = 5

Output

4

Sample 3 · Input

nums = [4,2,2,2,4,4,2,2], limit = 0

Output

3

No two values in a subarray are further apart than its largest and smallest values. So a subarray is valid exactly when its maximum minus its minimum is at most limit. In the second sample, [2, 4, 7, 2] has 7−2=57 - 2 = 5 and is valid. Extended one position to the left, [1, 2, 4, 7, 2] has 7−1=67 - 1 = 6, which is over the limit of 5.

Extending a window can raise its maximum or lower its minimum but cannot do the reverse, so a window that is over the limit stays over it when extended. That is the property the growing and shrinking window needs, so the same loop works: right moves forward one position at a time, and left moves forward while the window is over the limit. The loop also needs the window's maximum and minimum at every step, and reading through the window to find them is too slow. A window can hold 10510^5 values, and there are 10510^5 steps:

105×105=1010 reads10^5 \times 10^5 = 10^{10} \text{ reads}

That is 100 seconds at 10810^8 operations a second.