单调队列

239. 滑动窗口最大值

from typing import List


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        dq = [0] * len(nums)
        left = 0
        right = -1
        ans = list()
        for i in range(len(nums)):
            # 此处也可以写成if, 因此每次滑动只会前进一步
            while left <= right and i - k + 1 > dq[left]:
                left += 1
            while left <= right and nums[dq[right]] <= nums[i]:
                right -= 1
            right += 1
            dq[right] = i

            if i >= k - 1:
                ans.append(nums[dq[left]])
        # print(dq)
        return ans

    # 拓展：求滑动窗口中的最小值
    def minSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = list()
        left = 0
        right = - 1
        dq = [0] * len(nums)
        for i in range(len(nums)):

            # 如果所维护的窗口大小已经超过k则弹出最左边的元素
            while left <= right and i - k + 1 > dq[left]:
                left += 1

            # nums[i]是局部最小值，将其前面比它大的值都移除
            while left <= right and nums[dq[right]] >= nums[i]:
                right -= 1

            right += 1
            dq[right] = i

            if i >= k - 1:
                ans.append(nums[dq[left]])
        # print(dq)
        return ans

1438. 绝对差不超过限制的最长连续子数组

from typing import List
from collections import deque


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        max_dq, min_dq = deque(), deque()
        max_len = 0
        left = 0
        for right, num in enumerate(nums):
            while max_dq and num > max_dq[-1]:
                max_dq.pop()
            max_dq.append(num)
            while min_dq and num < min_dq[-1]:
                min_dq.pop()
            min_dq.append(num)

            # max_dq[0]是当前窗口最大值
            # min_dq[0]是当前窗口最小值
            while max_dq[0] - min_dq[0] > limit:
                # 窗口内不满足差值<=limit，从窗口左端开始丢弃值
                if nums[left] == max_dq[0]:
                    max_dq.popleft()
                if nums[left] == min_dq[0]:
                    min_dq.popleft()
                left += 1
            if max_dq[0] - min_dq[0] <= limit:
                max_len = max(max_len, right - left + 1)
        return max_len

from typing import List
import bisect


class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        i = j = 0
        st = []
        ans = 0
        while j < len(nums):
            bisect.insort(st, nums[j])
            while st[-1] - st[0] > limit:
                st.remove(nums[i])
                i += 1
            j += 1
            ans = max(ans, len(st))
        return ans

862. 和至少为 K 的最短子数组