MediumRating 1672

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

arrayqueuesliding-windowheap-priority-queueordered-setmonotonic-queue

在 LeetCode 上作答 ↗

解題說明

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

題目描述：給定一個整數陣列 nums 和一個整數 limit，找出最長的連續子陣列，使得子陣列中任意兩個元素的絕對差不超過 limit。回傳該子陣列的長度。

解題思路：使用滑動窗口 + 兩個單調佇列分別追蹤窗口內的最大值和最小值。一個單調遞減佇列維護最大值，一個單調遞增佇列維護最小值。當最大值 - 最小值 > limit 時，縮小窗口左邊界。每次更新窗口長度的最大值。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個元素最多進出每個佇列一次

空間複雜度：O(n) — 兩個單調佇列在最壞情況下各儲存 n 個元素

虛擬碼

1. Initialize two deques: maxDq (decreasing) and minDq (increasing)
2. Use sliding window with left pointer starting at 0
3. For each right pointer from 0 to n-1:
   a. Add nums[right] to maxDq (remove smaller elements from back)
   b. Add nums[right] to minDq (remove larger elements from back)
   c. While nums[maxDq.front()] - nums[minDq.front()] > limit:
      - Advance left pointer
      - Remove expired indices from front of both deques
   d. Update result = max(result, right - left + 1)
4. Return result

其他解法

方法二：有序多重集合（Multiset） 維護一個 multiset 代表當前窗口的元素。最大值為 *rbegin()，最小值為 *begin()。當差值超過 limit 時，從 multiset 中移除左端元素。每次操作 O(log n)，總時間 O(n log n)。

方法三：線段樹 / ST 表 使用線段樹或稀疏表（Sparse Table）支援區間最大值和最小值查詢。配合二分搜尋確定最長有效窗口。時間 O(n log n)。

延伸思考

如果 limit 不是固定值，而是隨時間變化的函數 limit(t)，你會如何處理？
如果子陣列不需要連續（可以跳過元素），這個問題會變成什麼？
兩個單調佇列的方法和 LeetCode 239（滑動窗口最大值）的關係是什麼？

Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit — CaffeCode