子数组的最小值之和 图解题解

这道题到底在问什么

输入

arr=[3,1,2,4]

输出

17 （10 个子数组的最小值累加）

最优解：一步一步想明白

1. 3记住口诀:维护值递增的下标栈,弹栈即结算贡献 arr[j] × left × right。下面每帧都在套它。
2. 4轮到 arr[0]=4(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 4 的下标,此刻弹出结算。当前 栈空。
3. 5把 arr[0]=4 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
4. 6轮到 arr[1]=2(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 2 的下标,此刻弹出结算。当前 栈顶 arr[0]=4。
5. 7栈顶 arr[0]=4 的值 ≥ 2,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 4×1×1=4。累加和到 4。
6. 8把 arr[1]=2 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
7. 9轮到 arr[2]=6(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 6 的下标,此刻弹出结算。当前 栈顶 arr[1]=2。
8. 10把 arr[2]=6 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
9. 11轮到 arr[3]=1(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 1 的下标,此刻弹出结算。当前 栈顶 arr[2]=6。
10. 12栈顶 arr[2]=6 的值 ≥ 1,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 6×1×1=6。累加和到 10。
11. 13栈顶 arr[1]=2 的值 ≥ 1,弹出结算。它在绿色这段里当最小值:左边可选 2 个起点、右边可选 2 个终点,共 2×2=4 个子数组,贡献 2×2×2=8。累加和到 18。
12. 14把 arr[3]=1 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
13. 15轮到 arr[4]=5(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 5 的下标,此刻弹出结算。当前 栈顶 arr[3]=1。
14. 16把 arr[4]=5 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
15. 17轮到 arr[5]=3(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 3 的下标,此刻弹出结算。当前 栈顶 arr[4]=5。
16. 18栈顶 arr[4]=5 的值 ≥ 3,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 5×1×1=5。累加和到 23。
17. 19把 arr[5]=3 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
18. 20轮到 arr[6]=7(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 7 的下标,此刻弹出结算。当前 栈顶 arr[5]=3。
19. 21把 arr[6]=7 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
20. 22轮到 arr[7]=2(紫色)。它可能成为栈内元素的「右边界」:凡栈里值 ≥ 2 的下标,此刻弹出结算。当前 栈顶 arr[6]=7。
21. 23栈顶 arr[6]=7 的值 ≥ 2,弹出结算。它在绿色这段里当最小值:左边可选 1 个起点、右边可选 1 个终点,共 1×1=1 个子数组,贡献 7×1×1=7。累加和到 30。
22. 24栈顶 arr[5]=3 的值 ≥ 2,弹出结算。它在绿色这段里当最小值:左边可选 2 个起点、右边可选 2 个终点,共 2×2=4 个子数组,贡献 3×2×2=12。累加和到 42。
23. 25把 arr[7]=2 自己压进栈(蓝色)。现在栈里下标对应的值严格递增,等着后面更小的元素来给它定右边界。
24. 26数组扫完了,栈里还剩 2 个下标没结算。补一个虚拟的「值 0 哨兵」当统一右边界,0 比谁都小,能把它们全部逼出来。
25. 27栈顶 arr[7]=2 的值 ≥ 哨兵 0,弹出结算。它在绿色这段里当最小值:左边可选 4 个起点、右边可选 1 个终点,共 4×1=4 个子数组,贡献 2×4×1=8。累加和到 50。
26. 28栈顶 arr[3]=1 的值 ≥ 哨兵 0,弹出结算。它在绿色这段里当最小值:左边可选 4 个起点、右边可选 5 个终点,共 4×5=20 个子数组,贡献 1×4×5=20。累加和到 70。
27. 29每个元素都被弹栈结算过一次,各自当最小值时的贡献全部累加,最终答案 70。每个下标只入栈、出栈各一次,整体 O(n)。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        stack = []
        ans = 0
        for i in range(len(arr) + 1):
            cur = 0 if i == len(arr) else arr[i]
            while stack and arr[stack[-1]] >= cur:
                j = stack.pop()
                left = j - (stack[-1] if stack else -1)
                right = i - j
                ans = (ans + arr[j] * left * right) % MOD
            stack.append(i)
        return ans

#include <vector>
using namespace std;
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const long long MOD = 1000000007;
        vector<int> st;
        long long ans = 0;
        for (int i = 0; i <= (int)arr.size(); ++i) {
            int cur = i == (int)arr.size() ? 0 : arr[i];
            while (!st.empty() && arr[st.back()] >= cur) {
                int j = st.back(); st.pop_back();
                int left = j - (st.empty() ? -1 : st.back());
                int right = i - j;
                ans = (ans + 1LL * arr[j] * left * right) % MOD;
            }
            st.push_back(i);
        }
        return ans;
    }
};

import java.util.*;
class Solution {
    public int sumSubarrayMins(int[] arr) {
        long MOD = 1_000_000_007L, ans = 0;
        Deque<Integer> st = new ArrayDeque<>();
        for (int i = 0; i <= arr.length; i++) {
            int cur = i == arr.length ? 0 : arr[i];
            while (!st.isEmpty() && arr[st.peek()] >= cur) {
                int j = st.pop();
                int left = j - (st.isEmpty() ? -1 : st.peek());
                int right = i - j;
                ans = (ans + (long) arr[j] * left * right) % MOD;
            }
            st.push(i);
        }
        return (int) ans;
    }
}

复杂度

面试官可能追问