2104. Sum of Subarray Ranges

Sum of Subarray Ranges

題目描述：給定整數陣列 nums，一個子陣列的 range 定義為其最大值減最小值。求所有子陣列 range 的總和。

解題思路：

直接觀察：range = max - min，因此：

所有子陣列 range 之和 = 所有子陣列最大值之和 - 所有子陣列最小值之和

這兩個子問題（所有子陣列最大值之和、所有子陣列最小值之和）都可以用貢獻法 + 單調棧在 O(n) 時間解決，與 LC 907「Sum of Subarray Minimums」完全對稱。

計算最小值之和：對每個 nums[i]，用單調遞增棧找：

• left_min[i]：到左側第一個嚴格更小元素的距離（左邊嚴格，避免重複）
• right_min[i]：到右側第一個更小或等於元素的距離（右邊允許等號）
• 貢獻 = nums[i] * left_min[i] * right_min[i]

計算最大值之和：對每個 nums[i]，用單調遞減棧找：

• left_max[i]：到左側第一個嚴格更大元素的距離
• right_max[i]：到右側第一個更大或等於元素的距離
• 貢獻 = nums[i] * left_max[i] * right_max[i]

最終答案 = 最大值總和 - 最小值總和。注意使用 long long 避免溢位。

時間複雜度：O(n) — 計算最小值之和與最大值之和各需兩次單調棧掃描，每次 O(n)，總計 O(n)。

空間複雜度：O(n) — left、right 輔助陣列和棧各 O(n)。

替代方案

方案一：暴力 O(n²)

枚舉所有子陣列 [i, j]，在擴展 j 的過程中同步維護當前最大值和最小值，每個子陣列貢獻 max - min 到答案。

long long ans = 0;
for (int i = 0; i < n; i++) {
    int mn = nums[i], mx = nums[i];
    for (int j = i; j < n; j++) {
        mn = min(mn, nums[j]);
        mx = max(mx, nums[j]);
        ans += mx - mn;
    }
}

時間 O(n²)，空間 O(1)。對於本題約束（n ≤ 1000），暴力也能通過，但理解 O(n) 方法更重要。

方案二：貢獻法（本解法）

將問題分解為「最大值之和」和「最小值之和」兩個子問題，各用單調棧在 O(n) 解決。等號邊界的非對稱處理（左嚴格、右寬鬆）是避免重複計算的關鍵，必須小心對稱地套用到最大值和最小值的計算上。

方案三：統一在一次掃描中計算

理論上可以在一次從左到右的掃描中同時維護兩個棧（一個遞增、一個遞減），同時更新最小值和最大值的貢獻。但這使程式碼難以理解，除非對效能有極端要求，否則不建議合併。

延伸問題

1. 與 LC 907 的關係：本題的最小值部分和 LC 907 完全相同。請確認：若將 sumSubarrayMins 加上 10⁹+7 取模，結果是否與 LC 907 完全一致？本題為何不需要取模（提示：檢查資料範圍，nums[i] 最大為 10⁵，n 最大為 1000）。

2. 等號邊界的對稱性：計算最小值時，左側用嚴格小於、右側用小於或等於。計算最大值時，左側用嚴格大於、右側用大於或等於。若兩邊都用嚴格比較，在有重複元素時會發生什麼錯誤？請用 nums = [2, 1, 2] 手動驗證。

3. 區間 range 查詢：若給定一個靜態陣列，需要多次查詢「子陣列 [l, r] 的 range」（單次查詢，非所有子陣列之和），可以用稀疏表（Sparse Table）在 O(n log n) 預處理後 O(1) 回答。與本題的單調棧方法相比，兩者各適用於什麼場景？