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

MediumView on LeetCode

Array Queue Sliding Window Heap (Priority Queue)Monotonic Queue

Intuition

Sliding window with a monotone deque tracking min and max. Window is valid when max-min <= limit.

Algorithm

1Two deques: max-deque (decreasing) and min-deque (increasing).
2Expand right. When max-min > limit, shrink left (remove from fronts of deques if index out of window).
3Track max window size.

Common Pitfalls

•Two separate deques for min and max. Shrink window when constraint violated.

1438.cpp

C++

class Solution {
 public:
  int longestSubarray(vector<int>& nums, int limit) {
    int ans = 1;
    deque<int> minQ;
    deque<int> maxQ;

    for (int l = 0, r = 0; r < nums.size(); ++r) {
      while (!minQ.empty() && minQ.back() > nums[r])
        minQ.pop_back();
      minQ.push_back(nums[r]);
      while (!maxQ.empty() && maxQ.back() < nums[r])
        maxQ.pop_back();
      maxQ.push_back(nums[r]);
      while (maxQ.front() - minQ.front() > limit) {
        if (minQ.front() == nums[l])
          minQ.pop_front();
        if (maxQ.front() == nums[l])
          maxQ.pop_front();
        ++l;
      }
      ans = max(ans, r - l + 1);
    }

    return ans;
  }
};

Was this solution helpful?