⚡Flashcard Drill➔
NeetCode #258LC-1438MediumSliding Window
← Back to All Problems

#258 · #1438 · Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit(绝对差不超过限制的最长连续子数组)

📌 Problem Statement & Constraints

Given an array of integers nums and an integer limit, return the size of the longest subarray such that the absolute difference between any two of its elements is at most limit. Constraints: 1 <= nums.length <= 10^5, 1 <= nums[i] <= 10^9, 0 <= limit <= 10^9.

💡 Core Algorithmic Approaches

  1. A window satisfies the condition exactly when max(window) - min(window) <= limit.
  2. So we need a sliding window with efficient access to its maximum and minimum -- two monotonic deques.
  3. One deque keeps indices in decreasing value order (front = maximum); the other keeps increasing order (front = minimum).
  4. When the difference exceeds limit, advance the left pointer and evict it from either deque if it is at the front.

💻 Benchmark Python3 Implementation

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        from collections import deque
        maxq = deque()                 # decreasing values, front is the max
        minq = deque()                 # increasing values, front is the min
        l = 0
        best = 0
        for r, x in enumerate(nums):
            while maxq and nums[maxq[-1]] <= x:
                maxq.pop()
            maxq.append(r)
            while minq and nums[minq[-1]] >= x:
                minq.pop()
            minq.append(r)
            while nums[maxq[0]] - nums[minq[0]] > limit:
                if maxq[0] == l:
                    maxq.popleft()
                if minq[0] == l:
                    minq.popleft()
                l += 1
            best = max(best, r - l + 1)
        return best

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each index is pushed and popped at most once from each deque.
💾 Space Complexity
O(n) for the two deques in the worst case.

⚠️ Interview Pitfalls & Follow-ups

  • Using max(window) and min(window) on the fly: O(n) per step, giving O(n^2).
  • Evicting from only one deque when shrinking: the leaving index may be at the front of either deque, so both must be checked.
  • Storing values instead of indices: you cannot tell whether the front has left the window.
  • Using < in the back-popping comparisons: either < or <= works, but be consistent; <= keeps the deques strictly monotone and slightly smaller.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🎯 Drill This Card Now➔

🧩 Related Sliding Window Problems