↓Skip to main content
  1. Posts/

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

·1 min·
Table of Contents

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

Solution 1 #

用两个单调队列分别维护滑动窗口中的最大值和最小值.

代码如下:

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        ans = 0
        max_q, min_q = deque(), deque()
        j = 0
        
        for i in range(len(nums)):
            while j < len(nums):
                while max_q and nums[max_q[-1]] <= nums[j]:
                    max_q.pop()
                max_q.append(j)
                while min_q and nums[min_q[-1]] >= nums[j]:
                    min_q.pop()
                min_q.append(j)
                if nums[max_q[0]] - nums[min_q[0]] > limit:
                    # max_q.pop()
                    # min_q.pop()
                    break
                j += 1

            ans = max(ans, j - i)

            if max_q and max_q[0] == i:
                max_q.popleft()
            if min_q and min_q[0] == i:
                min_q.popleft()
      
        return ans