MediumRating 1759

3835. Count Subarrays With Cost Less Than or Equal to K

arrayqueuemonotonic-queue

解題說明

Count Subarrays With Cost Less Than or Equal to K

題目描述：給定一個整數陣列 nums 和整數 k，定義一個子陣列的「成本」為該子陣列的最大值加上子陣列的長度。計算有多少個子陣列的成本小於等於 k。

解題思路：使用滑動窗口 + 單調佇列。固定右端點 r，找到最小的左端點 l，使得 max(nums[l..r]) + (r - l + 1) <= k。由於隨著窗口擴大，最大值不減且長度增加，成本是單調遞增的，因此可以用雙指標。

用單調遞減佇列維護窗口內的最大值。當成本 > k 時，移動左端點並從佇列中移除過期元素。對於每個右端點 r，合法的子陣列數量為 r - l + 1。

C++ 解法

複雜度分析

時間複雜度：O(n) — 每個元素最多進出單調佇列一次，雙指標各移動 O(n) 次。

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

虛擬碼

1. Initialize left pointer l = 0, count = 0
2. Maintain monotonic decreasing deque (stores indices) for window max
3. For each right pointer r from 0 to n-1:
   a. Push r onto deque (pop smaller elements from back)
   b. While cost = max(window) + length > k:
      - Advance l, remove expired front from deque
   c. Add (r - l + 1) to count
4. Return count

其他解法

二分搜尋 + 稀疏表 O(n log n)：對每個右端點 r，用二分搜尋找最小的 l 使成本 <= k。用稀疏表 (Sparse Table) O(1) 查詢區間最大值。整體 O(n log n)，比滑動窗口多一個 log 因子。

暴力法 O(n²)：枚舉所有子陣列，計算每個子陣列的最大值和長度。簡單但在 n 較大時超時。

延伸思考

如果成本定義為 max + min + length，如何維護兩個單調佇列？
若成本改為 sum + max（子陣列總和加最大值），能否仍用滑動窗口？
如果需要找到成本恰好等於 k 的子陣列數量（而非 <= k），如何修改？

Count Subarrays With Cost Less Than or Equal to K — CaffeCode