題目描述: 給定整數陣列 nums,一個子陣列是「連續的」若子陣列中任意兩個元素的絕對差不超過 2。計算所有連續子陣列的數量。
解題思路: 使用滑動窗口。維護窗口 [left, right] 使得窗口內的最大值 - 最小值 <= 2。可以用兩個單調佇列(一個維護最大值、一個維護最小值)來高效追蹤窗口的極值。
對於每個 right,擴展後如果 max - min > 2,就收縮 left 直到滿足條件。以 right 為右端點的合法子陣列數量為 right - left + 1。
時間複雜度: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)。