Chuỗi con liên tiếp dài nhất với chênh lệch tuyệt đối ≤ Limit (Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit) trong C++

Cho mảng nums và limit. Tìm độ dài chuỗi con liên tiếp dài nhất mà chênh lệch tuyệt đối giữa hai phần tử bất kỳ trong chuỗi con ≤ limit.

Ví dụ

Đầu vào: nums = [8,2,4,7], limit = 4
Đầu ra: 2 (chuỗi con [2,4] hoặc [4,7]).

Thuật toán cửa sổ trượt + Deque đơn điệu

Duy trì cửa sổ [j, i] và hai deque:

• maxD: giảm dần, đầu luôn là max cửa sổ.
• minD: tăng dần, đầu luôn là min cửa sổ.

Mở rộng i, cập nhật deque. Nếu maxD.front() - minD.front() > limit, thu hẹp j (bỏ phần tử khỏi deque nếu trùng đầu). Cập nhật độ dài max.

Triển khai C++

#include <bits/stdc++.h>
using namespace std;

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

Độ phức tạp

• Thời gian: O(N) - mỗi phần tử vào/ra deque tối đa 1 lần.
• Không gian: O(N) - deque lưu tối đa N phần tử.

Kết quả kiểm thử

Đầu vào: {7,8,2,4}, 4
Đầu ra: 2