題目描述：給定一個整數陣列 arr，求所有子陣列最小值的總和，結果對 10⁹+7 取模。
解題思路：
暴力枚舉所有子陣列需要 O(n²) 甚至 O(n³)，對於大輸入會超時。關鍵在於換個思路：不枚舉子陣列，而是對每個元素 arr[i] 計算「它作為最小值的子陣列有多少個」，然後貢獻 arr[i] * count 到答案。
對每個位置 i，定義：
left[i]：從 i 向左，能延伸到的最遠距離，即第一個嚴格小於 arr[i] 的位置（不含）到 i 的距離。若左邊沒有更小值，left[i] = i + 1。right[i]：從 i 向右，能延伸到的最遠距離，即第一個小於或等於 arr[i] 的位置（不含）到 i 的距離。若右邊沒有更小或等值，right[i] = n - i。注意左右邊界的嚴格/非嚴格處理是為了避免重複計算相等元素。以 arr[i] 作為最小值的子陣列數量 = left[i] * right[i]，貢獻 = arr[i] * left[i] * right[i]。
用兩次單調遞增棧（一次從左、一次從右）可在 O(n) 時間內求出所有 left[i] 和 right[i]。
時間複雜度：O(n) — 每個元素最多被推入和彈出棧各一次，兩次掃描共 O(n)。
空間複雜度：O(n) — left、right 陣列各 n 個元素，棧最多容納 n 個元素。
1. 初始化 left[0..n-1] 和 right[0..n-1] 陣列，以及一個空棧（存索引） 2. 從左到右遍歷 i = 0 到 n-1（計算 left[i]）： a. 當棧非空且 arr[栈顶] >= arr[i] 時，彈出棧頂 b. 若棧空，left[i] = i + 1；否則 left[i] = i - 棧頂索引 c. 將 i 推入棧 3. 清空棧 4. 從右到左遍歷 i = n-1 到 0（計算 right[i]）： a. 當棧非空且 arr[棧頂] > arr[i] 時，彈出棧頂（注意：等號方向相反） b. 若棧空，right[i] = n - i；否則 right[i] = 棧頂索引 - i c. 將 i 推入棧 5. 累加答案：ans += arr[i] * left[i] * right[i]，每步取模 6. 回傳 ans mod (10^9 + 7)
枚舉所有子陣列 [i, j]，維護當前最小值並累加。程式碼最直觀但對 n = 3×10⁴ 會超時。
long long ans = 0;
for (int i = 0; i < n; i++) {
int mn = arr[i];
for (int j = i; j < n; j++) {
mn = min(mn, arr[j]);
ans = (ans + mn) % MOD;
}
}
時間 O(n²)，空間 O(1)。僅適合小規模測試。
定義 dp[i] 為以 arr[i] 結尾的所有子陣列最小值之和。轉移時利用棧找到左邊第一個更小元素的位置 j，則 dp[i] = dp[j] + arr[i] * (i - j)。最終答案為 sum(dp)。
這種寫法在一次從左到右的掃描中同時完成計算，只需一個棧，程式碼較本解法更緊湊，且同樣是 O(n) 時間、O(n) 空間。
對每個元素獨立計算貢獻，概念最清晰，且左右邊界的計算完全對稱，便於理解和除錯。
Sum of Subarray Ranges（LC 2104）：若改成求所有子陣列 max - min 的總和，如何利用本題的技巧？提示：答案 = 所有子陣列最大值之和 - 所有子陣列最小值之和，各自用一次單調棧解決。
等號邊界處理：本解法中，左邊用嚴格小於、右邊用小於或等於，這樣能避免重複計算。若兩邊都用嚴格小於，哪些情況會出錯？請用 arr = [3, 1, 2, 4, 2, 1] 舉例驗證。
Online 版本：若要支援單點修改（修改 arr[i] 的值後立刻查詢新的總和），如何用線段樹維護？每個葉節點存 arr[i]，區間節點需要存哪些資訊才能 O(log n) 合併區間的子陣列最小值貢獻？