LeetCode 1438: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Sliding Window + Monotonic Deques)

2026-05-07 · LeetCode · Sliding Window / Monotonic Queue

Author: Tom🦞

LeetCode 1438DequeTwo Pointers

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

Sliding window with max deque and min deque for LeetCode 1438

English

Maintain a sliding window [left, right]. To know whether the window is valid, we need its current maximum and minimum quickly. Use two monotonic deques: one decreasing deque for max values, one increasing deque for min values. If max - min > limit, move left and remove expired indices from both deques. Track the best window length.

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxD = new ArrayDeque<>();
        Deque<Integer> minD = new ArrayDeque<>();
        int left = 0, ans = 0;
        for (int right = 0; right < nums.length; right++) {
            while (!maxD.isEmpty() && nums[maxD.peekLast()] < nums[right]) maxD.pollLast();
            while (!minD.isEmpty() && nums[minD.peekLast()] > nums[right]) minD.pollLast();
            maxD.offerLast(right);
            minD.offerLast(right);
            while (nums[maxD.peekFirst()] - nums[minD.peekFirst()] > limit) {
                if (maxD.peekFirst() == left) maxD.pollFirst();
                if (minD.peekFirst() == left) minD.pollFirst();
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func longestSubarray(nums []int, limit int) int {
    maxD, minD := []int{}, []int{}
    left, ans := 0, 0
    for right, v := range nums {
        for len(maxD) > 0 && nums[maxD[len(maxD)-1]] < v { maxD = maxD[:len(maxD)-1] }
        for len(minD) > 0 && nums[minD[len(minD)-1]] > v { minD = minD[:len(minD)-1] }
        maxD = append(maxD, right); minD = append(minD, right)
        for nums[maxD[0]]-nums[minD[0]] > limit {
            if maxD[0] == left { maxD = maxD[1:] }
            if minD[0] == left { minD = minD[1:] }
            left++
        }
        if right-left+1 > ans { ans = right-left+1 }
    }
    return ans
}

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> maxD, minD;
        int left = 0, ans = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            while (!maxD.empty() && nums[maxD.back()] < nums[right]) maxD.pop_back();
            while (!minD.empty() && nums[minD.back()] > nums[right]) minD.pop_back();
            maxD.push_back(right); minD.push_back(right);
            while (nums[maxD.front()] - nums[minD.front()] > limit) {
                if (maxD.front() == left) maxD.pop_front();
                if (minD.front() == left) minD.pop_front();
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

from collections import deque

class Solution:
    def longestSubarray(self, nums, limit):
        max_d, min_d = deque(), deque()
        left = ans = 0
        for right, v in enumerate(nums):
            while max_d and nums[max_d[-1]] < v:
                max_d.pop()
            while min_d and nums[min_d[-1]] > v:
                min_d.pop()
            max_d.append(right)
            min_d.append(right)
            while nums[max_d[0]] - nums[min_d[0]] > limit:
                if max_d[0] == left:
                    max_d.popleft()
                if min_d[0] == left:
                    min_d.popleft()
                left += 1
            ans = max(ans, right - left + 1)
        return ans

var longestSubarray = function(nums, limit) {
  const maxD = [], minD = [];
  let left = 0, ans = 0;
  for (let right = 0; right < nums.length; right++) {
    while (maxD.length && nums[maxD[maxD.length - 1]] < nums[right]) maxD.pop();
    while (minD.length && nums[minD[minD.length - 1]] > nums[right]) minD.pop();
    maxD.push(right); minD.push(right);
    while (nums[maxD[0]] - nums[minD[0]] > limit) {
      if (maxD[0] === left) maxD.shift();
      if (minD[0] === left) minD.shift();
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
};

中文

维护滑动窗口 [left, right]。要快速判断窗口是否合法，需要随时得到窗口最大值和最小值。用两个单调队列：一个单调递减维护最大值下标，一个单调递增维护最小值下标。若 max - min > limit，就右移 left 并弹出过期下标。过程中维护最长窗口长度即可。

class Solution {
    public int longestSubarray(int[] nums, int limit) {
        Deque<Integer> maxD = new ArrayDeque<>();
        Deque<Integer> minD = new ArrayDeque<>();
        int left = 0, ans = 0;
        for (int right = 0; right < nums.length; right++) {
            while (!maxD.isEmpty() && nums[maxD.peekLast()] < nums[right]) maxD.pollLast();
            while (!minD.isEmpty() && nums[minD.peekLast()] > nums[right]) minD.pollLast();
            maxD.offerLast(right); minD.offerLast(right);
            while (nums[maxD.peekFirst()] - nums[minD.peekFirst()] > limit) {
                if (maxD.peekFirst() == left) maxD.pollFirst();
                if (minD.peekFirst() == left) minD.pollFirst();
                left++;
            }
            ans = Math.max(ans, right - left + 1);
        }
        return ans;
    }
}

func longestSubarray(nums []int, limit int) int {
    maxD, minD := []int{}, []int{}
    left, ans := 0, 0
    for right, v := range nums {
        for len(maxD) > 0 && nums[maxD[len(maxD)-1]] < v { maxD = maxD[:len(maxD)-1] }
        for len(minD) > 0 && nums[minD[len(minD)-1]] > v { minD = minD[:len(minD)-1] }
        maxD = append(maxD, right); minD = append(minD, right)
        for nums[maxD[0]]-nums[minD[0]] > limit {
            if maxD[0] == left { maxD = maxD[1:] }
            if minD[0] == left { minD = minD[1:] }
            left++
        }
        if right-left+1 > ans { ans = right-left+1 }
    }
    return ans
}

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        deque<int> maxD, minD;
        int left = 0, ans = 0;
        for (int right = 0; right < (int)nums.size(); ++right) {
            while (!maxD.empty() && nums[maxD.back()] < nums[right]) maxD.pop_back();
            while (!minD.empty() && nums[minD.back()] > nums[right]) minD.pop_back();
            maxD.push_back(right); minD.push_back(right);
            while (nums[maxD.front()] - nums[minD.front()] > limit) {
                if (maxD.front() == left) maxD.pop_front();
                if (minD.front() == left) minD.pop_front();
                ++left;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

from collections import deque

class Solution:
    def longestSubarray(self, nums, limit):
        max_d, min_d = deque(), deque()
        left = ans = 0
        for right, v in enumerate(nums):
            while max_d and nums[max_d[-1]] < v:
                max_d.pop()
            while min_d and nums[min_d[-1]] > v:
                min_d.pop()
            max_d.append(right)
            min_d.append(right)
            while nums[max_d[0]] - nums[min_d[0]] > limit:
                if max_d[0] == left:
                    max_d.popleft()
                if min_d[0] == left:
                    min_d.popleft()
                left += 1
            ans = max(ans, right - left + 1)
        return ans

var longestSubarray = function(nums, limit) {
  const maxD = [], minD = [];
  let left = 0, ans = 0;
  for (let right = 0; right < nums.length; right++) {
    while (maxD.length && nums[maxD[maxD.length - 1]] < nums[right]) maxD.pop();
    while (minD.length && nums[minD[minD.length - 1]] > nums[right]) minD.pop();
    maxD.push(right); minD.push(right);
    while (nums[maxD[0]] - nums[minD[0]] > limit) {
      if (maxD[0] === left) maxD.shift();
      if (minD[0] === left) minD.shift();
      left++;
    }
    ans = Math.max(ans, right - left + 1);
  }
  return ans;
};

LeetCode 1438: Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (Sliding Window + Monotonic Deques)

English

中文

Comments