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

tags: `Weekly Contest 187` `陣列(Array)` `佇列(Queue)` `滑動窗口(Sliding Window)` `有序集合(Ordered Set)` `堆積(Heap)` `單調佇列(Monotonic Queue)`

題意

給定一個整數陣列 $nums$ 和一個整數 $limit$ ，請你返回最長連續子陣列的長度，該子陣列中的任意兩個元素之間的絕對差必須小於或者等於 $limit$ 。

如果不存在滿足條件的子陣列，則返回 $0$ 。

思路：滑動窗口(Sliding Window)

這種連續子區間需滿足某些條件的問題，通常可以使用滑動窗口(Sliding Window) 的技巧來解決。我們可以維護一個窗口，使得窗口內的最大值和最小值的差不超過 $limit$ 。當窗口內包含的子區間不再滿足條件時，我們縮小窗口的左邊界，直到條件再次滿足。

而維護窗口內的最大值和最小值，可以使用有序集合(Ordered Set) 、堆積(Heap) 或者單調佇列(Monotonic Queue) 來實現。

方法一：滑動窗口(Sliding Window) + 有序集合(Sorted Set)

使用一個有序集合(Ordered Set) $s$ 來維護當前窗口內的所有元素。有序集合能夠讓我們快速獲取窗口內的最大值和最小值。

在本題中，我們需要維護窗口內的所有元素，因此需要使用有序的多重集合(multiset)。多重集合是一種集合，其中元素可以重複出現。在 Python 中，我們可以使用 sortedcontainers 提供的 SortedList 類別；在 C++ 中，我們可以使用 multiset 。

具體步驟如下：

初始化左指針 $left$ 以及答案 $ans$ 。
枚舉子陣列的右端點 $right$ ：
a. 將當前元素加入有序集合。
b. 如果集合中最大值和最小值的差超過了 $limit$ ，則移動左指針，並從集合中移除對應的元素，直到滿足條件。
c. 更新答案，取當前窗口大小和已知最大長度的較大值。
返回最終答案 $ans$ 即可。

複雜度分析

時間複雜度： $O(n \log n)$ $O (n lo g n)$ ，其中 $n$ $n$ 是陣列的長度。
- 每次插入和刪除操作在有序集合中需要 $O(\log n)$ 的時間。
空間複雜度： $O(n)$ ，用於存儲有序集合中的元素。

from sortedcontainers import SortedList

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        sl = SortedList()
        ans = left = 0
        for right in range(n):
            sl.add(nums[right])
            while sl[-1] - sl[0] > limit:
                sl.remove(nums[left])
                left += 1
            ans = max(ans, right - left + 1)
        return ans

class Solution {
public:
    int longestSubarray(vector<int>& nums, int limit) {
        int n = nums.size();
        multiset<int> s;
        int ans = 0, left = 0;
        for (int right = 0; right < n; right++) {
            s.insert(nums[right]);
            while (*s.rbegin() - *s.begin() > limit) {
                s.erase(s.find(nums[left]));
                left++;
            }
            ans = max(ans, right - left + 1);
        }
        return ans;
    }
};

方法二：滑動窗口(Sliding Window) + 單調佇列(Monotonic Queue)

由於我們只需要維護窗口內的最大值和最小值，而在當前窗口最大值左邊的值顯然不會再成為窗口內的最大值，因此在維護最大值時，我們可以將這些值從佇列中移除，換句話說，我們只需考慮右側不存在更大值的元素。同理，維護最小值時也是如此。故我們可以使用單調佇列(Monotonic Queue) 來維護窗口內的最大值和最小值。

而在處理完兩個單調佇列後，我們只需檢查兩個佇列的首元素之差是否超過 $limit$ ，如果超過 $limit$ ，則需要移動左指針，並更新佇列。

具體步驟如下：

初始化兩個雙端佇列(Deque) $q_{\text{min}}$ 和 $q_{\text{max}}$ ，分別用於維護窗口內的最小值和最大值。
初始化左指針 $left$ 以及答案 $ans$ 。
枚舉子陣列的右端點 $right$ ：
a. 更新 $q_{\text{min}}$ 和 $q_{\text{max}}$ ，保持 $q_{\text{min}}$ 的單調遞增性和 $q_{\text{max}}$ 的單調遞減性。
b. 如果 $q_{\text{max}}$ 的首元素減去 $q_{\text{min}}$ 的首元素大於 $limit$ ，則移動左指針，並更新佇列。
c. 更新答案，取當前窗口大小和已知最大長度的較大值。
返回最終答案 $ans$ 即可。

複雜度分析

時間複雜度： $O(n)$ $O (n)$ ，其中 $n$ $n$ 是陣列的長度。
- 每個元素最多被插入和刪除一次。
空間複雜度： $O(n)$ ，用於存儲兩個雙端佇列。

class Solution:
    def longestSubarray(self, nums: List[int], limit: int) -> int:
        n = len(nums)
        q_min, q_max = deque(), deque() # 分別維護最小值和最大值的下標
        ans = left = 0
        for right in range(n):
            while q_min and nums[right] < q_min[-1]: # 維護 q_min 的單調遞增性
                q_min.pop()
            while q_max and nums[right] > q_max[-1]: # 維護 q_max 的單調遞減性
                q_max.pop()
            q_min.append(nums[right])
            q_max.append(nums[right])
            while q_max[0] - q_min[0] > limit: # 當最大值和最小值的差值大於 limit 時，移動 left
                if nums[left] == q_min[0]:
                    q_min.popleft()
                if nums[left] == q_max[0]:
                    q_max.popleft()
                left += 1
            ans = max(ans, right - left + 1)
        return ans

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