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

Tags: Medium Array Sliding Window

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

---

Given an array of integers nums and an integer limit, return the size of the longest continuous subarray such that the absolute difference between any two elements is less than or equal to limit.

In case there is no subarray satisfying the given condition return 0.

Example 1:

Input: nums = [8,2,4,7], limit = 4
Output: 2 
Explanation: All subarrays are: 
[8] with maximum absolute diff |8-8| = 0 <= 4.
[8,2] with maximum absolute diff |8-2| = 6 > 4. 
[8,2,4] with maximum absolute diff |8-2| = 6 > 4.
[8,2,4,7] with maximum absolute diff |8-2| = 6 > 4.
[2] with maximum absolute diff |2-2| = 0 <= 4.
[2,4] with maximum absolute diff |2-4| = 2 <= 4.
[2,4,7] with maximum absolute diff |2-7| = 5 > 4.
[4] with maximum absolute diff |4-4| = 0 <= 4.
[4,7] with maximum absolute diff |4-7| = 3 <= 4.
[7] with maximum absolute diff |7-7| = 0 <= 4. 
Therefore, the size of the longest subarray is 2.

Example 2:

Input: nums = [10,1,2,4,7,2], limit = 5
Output: 4 
Explanation: The subarray [2,4,7,2] is the longest since the maximum absolute diff is |2-7| = 5 <= 5.

Example 3:

Input: nums = [4,2,2,2,4,4,2,2], limit = 0
Output: 3

Constraints:

• 1 <= nums.length <= 10^5
• 1 <= nums[i] <= 10^9
• 0 <= limit <= 10^9

---

用两个双端队列记录区间[pos, i]之间的最大值和最小值，如果区间的最大值和最小值的差值大于limit，那么pos位置右移一个单位，同时去检验最大值队列和最小值队列的首元素的下标是否小于pos，小于pos意味着已经不在窗口[pos, i]之间了，需要删除。

每个元素进队和出队，最多遍历两次，时间复杂度是$O(n)$， 空间复杂度$O(n)$。

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int pos = 0;
        deque<int> maxQueue, minQueue;
        int res = 0;
        for (int i = 0; i < n; ++i) {
            while (!maxQueue.empty() && nums[maxQueue.back()] < nums[i]) maxQueue.pop_back();
            maxQueue.push_back(i);

            while (!minQueue.empty() && nums[minQueue.back()] > nums[i]) minQueue.pop_back();
            minQueue.push_back(i);

            while (!maxQueue.empty() && !minQueue.empty() && 
                nums[maxQueue.front()] - nums[minQueue.front()] > limit) {
                ++pos;
                while (!maxQueue.empty() && maxQueue.front() < pos) maxQueue.pop_front();
                while (!minQueue.empty() && minQueue.front() < pos) minQueue.pop_front();
            }
            res = max(res, i - pos + 1);
        }

        return res;
    }
};