1438. 絕對差不超過限制的最長連續子數組

思路

子陣列的元素是連續的，可以視為一個窗口。
問題問的就是「窗口內的最大數值減去最小數值 $\leq{limit}$ 」的最長子陣列有多長。
窗口內的最大值，跟239. 滑動窗口最大值求的方法相同，最小值只要反過來就行。

• 窗口越大，最大值只會越來越大，單調遞增。
• 窗口越小，最小值只會越來越小，單調遞減。

也就是說，窗口越大，就越不可能達成目標，
因此在擴張右邊界時，如果不達標，就沒有必要繼續往右擴，而是開始縮減左端。

程式碼

1. 單調隊列

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        // 最大跟最小值的差要 < limit 
        int n = nums.size();
        deque<int> mx_q, mn_q;
        int left = 0, res = 0;
        for(int i = 0; i < n; i++) {
            while(!mn_q.empty() && nums[mn_q.back()] >= nums[i]) {
                mn_q.pop_back();
            }
            mn_q.push_back(i);
            while(!mx_q.empty() && nums[mx_q.back()] <= nums[i]) {
                mx_q.pop_back();
            }
            mx_q.push_back(i);
            while(nums[mx_q.front()] - nums[mn_q.front()] > limit) {
                // 最大最小值的差距太大，需要清除
                if(mx_q.front() == left) {
                    mx_q.pop_front();
                }
                // 最大跟最小值可以是同一個數字，所以不能用 else
                if(mn_q.front() == left) {
                    mn_q.pop_front();
                }
                left++;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

2. 單調隊列 數組模擬

class Solution {
private:
    static const int MX = 1e5 + 1;
    int mx_q[MX], mn_q[MX];
public:
    int longestSubarray(vector<int>& nums, int limit) {
        // 最大跟最小值的差要 < limit 
        int n = nums.size();
        int left, mx_left, mx_right, mn_left, mn_right, res;
        left = mx_left = mx_right = mn_left = mn_right = res = 0;
        for(int i = 0; i < n; i++) {
            while(mn_left != mn_right && nums[mn_q[mn_right - 1]] >= nums[i]) {
                mn_right--;
            }
            mn_q[mn_right++] = i;
            while(mx_left != mx_right && nums[mx_q[mx_right - 1]] <= nums[i]) {
                mx_right--;
            }
            mx_q[mx_right++] = i;
            while(nums[mx_q[mx_left]] - nums[mn_q[mn_left]] > limit) {
                // 最大最小值的差距太大，需要清除
                if(mx_q[mx_left] == left) {
                    mx_left++;
                }
                // 最大跟最小值可以是同一個數字，所以不能用 else
                if(mn_q[mn_left] == left) {
                    mn_left++;
                }
                left++;
            }
            res = max(res, i - left + 1);
        }
        return res;
    }
};

複雜度分析

• 時間複雜度：$O(n)$
• 空間複雜度：$O(n)$