1438. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit

https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/

Sliding Window, 有点像next greater element

from collections import deque
class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        res = 0
        mmin = deque()
        mmax = deque()
        i = 0
        for j,num in enumerate(nums):
            #这一段保证mmin 像这样:  2 3 4 5 6
            while len(mmin) > 0 and num < mmin[-1]:
                mmin.pop()
            #mmax: 7 6 5 4 3
            while len(mmax) > 0 and num > mmax[-1]:
                mmax.pop()
            mmin.append(num)
            mmax.append(num)
            while len(mmax) and len(mmin) and mmax[0] - mmin[0] > limit:
                if mmax[0] == nums[i]:
                    mmax.popleft()
                if mmin[0] == nums[i]: 
                    mmin.popleft()
                i+=1
            res = max(res,j-i+1)
        return res
        

while len(mmax) and len(mmin) and mmax[0] - mmin[0] > limit:
                if mmax[0] == nums[i]:
                    mmax.popleft()
                if mmin[0] == nums[i]: 
                    mmin.popleft()

这一段是最重要的因为

mmin: 2 3 4 5 6

mmax: 7 6 5 4 3

如果当前A[i] 只是 3 这种既不是最大又不是最小的无关紧要的值时，mmin 和

mmax是不需要更新的，只有当A[i] 是mmin和mmax中的极值时，A[i]被删除才会影响这两个deque