Hi,
the solutions in Python are inefficient, since they recompute min and max for every step, result in a O(n^2) solution.
Observe that you can use queues to track the min and max elements for every step in an efficient way.
I suggest to use my solution as an editorial one:
from collections import deque
import time
class Solution:
# @param A : list of integers
# @param B : integer
# @return an integer
def solve(self, A, B):
if B < 0:
return 0
n = len(A)
s_idx = 0
longest_dist = 1
min_queue = deque()
max_queue = deque()
e_idx = s_idx
while e_idx < n:
curr_elem = A[e_idx]
while min_queue and min_queue[-1] > curr_elem:
min_queue.pop()
while max_queue and max_queue[-1] < curr_elem:
max_queue.pop()
min_queue.append(curr_elem)
max_queue.append(curr_elem)
while max_queue[0] - min_queue[0] >= B:
while A[s_idx] != min_queue[0] and A[s_idx] != max_queue[0]:
s_idx += 1
if A[s_idx] == min_queue[0]:
min_queue.popleft()
if A[s_idx] == max_queue[0]:
max_queue.popleft()
s_idx += 1
if e_idx - s_idx + 1 > longest_dist:
longest_dist = e_idx - s_idx + 1
e_idx += 1
return longest_dist