HardRating 2855
3420. Count Non-Decreasing Subarrays After K Operations
arraystacksegment-treequeuesliding-windowmonotonic-stackmonotonic-queue
解題說明
Count Non-Decreasing Subarrays After K Operations
題目描述：給定一個整數陣列 nums 和整數 k。你可以對一個子陣列執行最多 k 次操作：每次操作選擇一個元素將其減少 1。計算有多少個子陣列在最多 k 次操作後可以變成非遞減的。
解題思路：使用滑動視窗。對於固定的右端點 r，找到最小的左端點 l 使得子陣列 nums[l..r] 可以用至多 k 次操作變成非遞減。關鍵觀察：為了讓子陣列非遞減，每當 nums[i] > nums[i+1] 時需要減少前面的元素。使用單調棧維護「需要下降到的目標值」序列，並追蹤所需的操作次數。當操作次數超過 k 時，收縮左端點。具體而言，維護一個單調遞增棧，棧中記錄 (值, 影響的元素數量)，當新元素小於棧頂時，需要將棧頂的元素都「降低」到新元素值，這些降低的總量就是所需操作數。
C++ 解法
複雜度分析
時間複雜度：O(n) — 每個元素最多進出單調棧一次，滑動視窗整體為線性。
空間複雜度：O(n) — 單調棧最多存 O(n) 個元素。
虛擬碼
1. Initialize sliding window [l, r], cost = 0, monotonic stack
2. For each r = 0 to n-1:
a. While stack top value > nums[r]:
Pop (val, count); cost += (val - nums[r]) * count
Accumulate count
b. Push (nums[r], accumulated_count) to stack
c. While cost > k:
Remove contribution of nums[l] from front of stack
Shrink window: l++
d. ans += (r - l + 1)
3. Return ans其他解法
暴力 + 貪心 O(n²)：對每個子陣列，貪心地計算使其非遞減所需的最少操作數（從右到左，遇到遞減就降低左邊元素）。在 n 大時超時。
線段樹 + 滑動視窗 O(n log n)：用線段樹維護視窗內的「需要降低的成本」，支援區間更新和查詢。比單調棧方案慢一個 log 因子但更通用。
延伸思考
- 如果操作改為「增加 1」（而非減少 1），演算法如何調整？
- 如果要求嚴格遞增（而非非遞減），所需操作數的計算如何變化？
- 如果 k 非常大（接近 n × max(nums)），是否有更簡單的公式直接計算答案？