MediumRating 1940

2762. Continuous Subarrays

arrayqueuesliding-windowheap-priority-queueordered-setmonotonic-queue

在 LeetCode 上作答 ↗

解題說明

Continuous Subarrays

題目描述：給定整數陣列 nums，一個子陣列是「連續的」若子陣列中任意兩個元素的絕對差不超過 2。計算所有連續子陣列的數量。

解題思路：使用滑動窗口。維護窗口 [left, right] 使得窗口內的最大值 - 最小值 <= 2。可以用兩個單調佇列（一個維護最大值、一個維護最小值）來高效追蹤窗口的極值。

對於每個 right，擴展後如果 max - min > 2，就收縮 left 直到滿足條件。以 right 為右端點的合法子陣列數量為 right - left + 1。

C++ 解法

複雜度分析

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

空間複雜度：O(n) — 兩個單調佇列

虛擬碼

1. Initialize left = 0, two deques (maxQ for max, minQ for min)
2. For each right from 0 to n-1:
   a. Add right to maxQ (maintain decreasing order)
   b. Add right to minQ (maintain increasing order)
   c. While max - min > 2:
      - Advance left
      - Remove expired indices from both deques
   d. Add (right - left + 1) to answer
3. Return answer

其他解法

有序多重集合法：用 multiset 維護窗口內的元素。最大值 = *rbegin()，最小值 = *begin()。擴展時插入，收縮時刪除。每次操作 O(log n)，總時間 O(n log n)。實作簡單但比單調佇列慢。
TreeMap / 計數映射法：用 map<int,int> 記錄窗口內每個值的出現次數。最大最小值分別為 rbegin()->first 和 begin()->first。同樣 O(n log n)。

延伸思考

如果條件改為任意兩元素差不超過 k（而非固定的 2），演算法如何泛化？
如果要找最長的連續子陣列（而非計數），只需要追蹤最大窗口大小即可。
如果陣列是環形的（首尾相連），如何計算連續子陣列數量？

Continuous Subarrays — CaffeCode