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

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

## 題目大意

給定一個整數陣列 `nums` 和一個整數 `limit`，回傳最長的非空子陣列大小，使得該子陣列中任意兩個元素的絕對差小於或等於 `limit`。

## 思考

### Algo 1

用一個 treeset 來維護，由於這會是有序的，故我們能很輕易的找出範圍內最大值跟最小值，檢查有沒有在 `limit` 內

class Solution
{
public:
    int longestSubarray(vector<int> &nums, int limit)
    {
        multiset<int> mulS;
        const int n = nums.size();
        int ans = 0, l = 0, r = 0;

        while (r < n)
        {
            mulS.insert(nums[r++]);

            while (*prev(mulS.end()) - *mulS.begin() > limit)
                mulS.erase(mulS.find(nums[l++]));

            ans = max(ans, r - l);
        }

        return ans;
    }
};

但維護 treeset 時間複雜度要 $O(nlogn)$

### Algo 2

演算法本身還是 sliding window 但跟 algo 1 不一樣的地方在於我們採用了不同的資料結構達成目的

這邊我們用了兩個 deque 解題，將時間複雜度變成 $O(n)$

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

        for (auto l = nums.begin(), r = nums.begin(); r != end; ++r)
        {
            while (!minQ.empty() && minQ.back() > *r)
                minQ.pop_back();
            minQ.push_back(*r);

            while (!maxQ.empty() && maxQ.back() < *r)
                maxQ.pop_back();
            maxQ.push_back(*r);

            while (maxQ.front() - minQ.front() > limit)
            {
                if (minQ.front() == *l)
                    minQ.pop_front();
                if (maxQ.front() == *l)
                    maxQ.pop_front();

                ++l;
            }

            ans = max(ans, static_cast<int>(r - l + 1));
        }

        return ans;
    }
};

參考自：[suyalneeraj09 的解法](https://leetcode.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solutions/5354833/easy-java-python3-c-solution-30-ms)