LeetCode 907. 子数组的最小值之和——单调栈贡献法的通用模式

适读人群：Java 中级工程师、备战面试的同学 | 阅读时长：约22分钟 | 难度：中等偏难

---

开篇故事

这道题是我刷题生涯里第一道让我感受到「数学之美」的算法题。

刚看题目的时候，脑子里是：枚举所有子数组，每个子数组找最小值，然后求和。写完之后，O(n²) 的时间复杂度，小数据没问题，大数据直接超时。

然后我开始想有没有更聪明的方法。在某个深夜，我突然想到了一个反向思考的角度：与其问「每个子数组的最小值是什么」，不如问「每个元素作为最小值时，它贡献了多少次？」

这就是「贡献法」的核心思想，也是单调栈在区间统计问题中最强大的应用模式。掌握了这个思想，一批「子数组最大/最小值之和」的题都可以用同一个框架解决。

---

一、题目解析

题目描述：

给定一个整数数组 arr，找到所有 子数组 的最小值之和。

结果对 10^9 + 7 取余。

示例：

输入：arr = [3,1,2,4]
输出：17
解释：所有子数组：
[3]->3, [1]->1, [2]->2, [4]->4
[3,1]->1, [1,2]->1, [2,4]->2
[3,1,2]->1, [1,2,4]->1
[3,1,2,4]->1
和：3+1+2+4+1+1+2+1+1+1 = 17

约束：

• 1 <= arr.length <= 3 * 10^4
• 1 <= arr[i] <= 3 * 10^4

核心问题： 数组长度最大 30000，子数组数量是 O(n²)，直接枚举必然超时。

---

二、解法一：暴力枚举所有子数组

思路分析

枚举所有子数组的左右端点，维护当前最小值，累加。

class Solution {
    public int sumSubarrayMins(int[] arr) {
        final int MOD = 1_000_000_007;
        int n = arr.length;
        long result = 0;
        
        for (int i = 0; i < n; i++) {
            int minVal = arr[i];
            for (int j = i; j < n; j++) {
                minVal = Math.min(minVal, arr[j]); // 维护最小值
                result = (result + minVal) % MOD;
            }
        }
        
        return (int) result;
    }
}

复杂度分析

• 时间复杂度：O(n²)。双重循环。
• 空间复杂度：O(1)。

数据 n=3×10^{4，n²=9×10}8，必然超时。

---

三、解法二：单调栈 + 贡献法（基础版）

核心思想：贡献法

换个角度思考：对于每个元素 arr[i]，统计它作为最小值的子数组有多少个，然后贡献值 = arr[i] × 子数组数量。

一个元素 arr[i] 作为某个子数组的最小值，意味着这个子数组里没有比 arr[i] 更小的元素。那么，以 arr[i] 为最小值的子数组，必须满足：

• 左边界在 (上一个更小元素位置, i] 之间
• 右边界在 [i, 下一个更小元素位置) 之间

设：

• left[i] = i 与「左边第一个更小元素」之间的距离（即 i - leftSmaller[i]）
• right[i] = i 与「右边第一个更小等于元素」之间的距离（即 rightSmallerEqual[i] - i）

则 arr[i] 作为最小值的子数组数量 = left[i] × right[i]。

为什么右边是「更小等于」而非「更小」？ 为了处理重复元素，避免同一个子数组被多个相同值的最小元素重复计算。具体来说：左边用「严格更小」，右边用「小于等于」（即遇到相等也停止）。

class Solution {
    public int sumSubarrayMins(int[] arr) {
        final int MOD = 1_000_000_007;
        int n = arr.length;
        
        int[] left = new int[n];  // i 到左边第一个更小元素的距离（不含）
        int[] right = new int[n]; // i 到右边第一个更小等于元素的距离（不含）
        
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 计算 left[i]：左边第一个严格更小元素
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                stack.pop();
            }
            left[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
            stack.push(i);
        }
        
        stack.clear();
        
        // 计算 right[i]：右边第一个小于等于的元素
        for (int i = n - 1; i >= 0; i--) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                stack.pop();
            }
            right[i] = stack.isEmpty() ? n - i : stack.peek() - i;
            stack.push(i);
        }
        
        // 贡献法求和
        long result = 0;
        for (int i = 0; i < n; i++) {
            result = (result + (long) arr[i] * left[i] * right[i]) % MOD;
        }
        
        return (int) result;
    }
}

复杂度分析

• 时间复杂度：O(n)。两次单调栈各 O(n)。
• 空间复杂度：O(n)。

---

四、解法三（最优）：单次遍历单调栈

核心思想

上面的解法用了两次遍历，每次单独计算 left 和 right。实际上可以在一次遍历中完成所有计算：当一个元素从栈中弹出时，它左边的边界（弹出后的新栈顶）和右边的边界（触发弹出的当前元素）都已知，可以立即计算贡献。

完整代码

class Solution {
    public int sumSubarrayMins(int[] arr) {
        final int MOD = 1_000_000_007;
        int n = arr.length;
        long result = 0;
        
        // 单调递增栈（栈底到栈顶递增），存下标
        Deque<Integer> stack = new ArrayDeque<>();
        
        // 遍历到 n（哨兵）确保所有元素都被弹出
        for (int i = 0; i <= n; i++) {
            // 当 i==n 时，强制弹出所有剩余元素（虚拟哨兵值为0或负无穷）
            int curVal = (i == n) ? 0 : arr[i];
            
            while (!stack.isEmpty() && arr[stack.peek()] >= curVal) {
                int mid = stack.pop();
                // left boundary: 弹出后的栈顶（若栈空则为-1）
                int leftBound = stack.isEmpty() ? -1 : stack.peek();
                // right boundary: 当前位置 i（但i==n时实际是n-1+1=n）
                int rightBound = i;
                
                // 以 arr[mid] 为最小值的子数组数量
                long count = (long)(mid - leftBound) * (rightBound - mid);
                result = (result + arr[mid] * count) % MOD;
            }
            
            if (i < n) stack.push(i);
        }
        
        return (int) result;
    }
}

注意： 这里弹出条件用 >=（即右边用「严格小于」来弹出），左边在找第一个更小时用的是「弹出时新栈顶」。为避免重复计算相等元素，我们需要在左边或右边其中一个使用严格不等。这里选择右边触发弹出时用「严格小于 curVal」（即 arr[stack.peek()] >= curVal 时弹出），等效于右边是「小于等于」。

手动模拟

以 arr = [3,1,2,4] 为例：

i	curVal	弹出操作	贡献计算	结果
0	3	无	-	栈:[0]
1	1	弹0(3)，left=-1，right=1	3×(0-(-1))×(1-0)=3×1×1=3	3
1	1	压入1	-	栈:[1]
2	2	无	-	栈:[1,2]
3	4	无	-	栈:[1,2,3]
4(n)	0	弹3(4)，left=2，right=4	4×(3-2)×(4-3)=4	7
4(n)	0	弹2(2)，left=1，right=4	2×(2-1)×(4-2)=4	11
4(n)	0	弹1(1)，left=-1，right=4	1×(1-(-1))×(4-1)=6	17

最终结果：17，正确！

复杂度分析

• 时间复杂度：O(n)。每个元素最多入栈出栈各一次。
• 空间复杂度：O(n)。

---

五、举一反三

贡献法 + 单调栈是一类题的通用框架：

题目	变体
LeetCode 2104. 子数组范围和	用「子数组最大值之和 - 子数组最小值之和」
LeetCode 84. 柱状图最大矩形	每个柱作为最矮柱时能覆盖的最大面积
LeetCode 1856. 子数组最小乘积的最大值	贡献法+前缀和

贡献法模板：

// 计算每个元素作为[最大/最小]值时，覆盖多少子数组
// left[i] = i 到左边第一个[更大/更小]元素的距离
// right[i] = i 到右边第一个[更大/更小]元素的距离
// 子数组数量 = left[i] * right[i]
// 贡献 = arr[i] * left[i] * right[i]

---

六、踩坑实录

坑一：重复元素导致重复计数

如果数组里有重复元素，比如 [1,1]，子数组有 [1]（左）、[1]（右）、[1,1]，最小值分别是 1、1、1，总和是 3。

如果我们对两个 1 都用「严格更小」来计算边界，两个 1 的 left×right 分别是 1×2=2 和 2×1=2，总贡献是 1×2 + 1×2 = 4，比正确答案 3 多了 1。原因就是 [1,1] 这个子数组被两个 1 各计算了一次。

解决方法：左边用严格更小（<），右边用小于等于（<=），或者反过来。这样每个子数组只被一个最小值的「最左出现位置」计算一次。

坑二：溢出问题

arr[i] 最大是 3×10^4，left[i] 和 right[i] 最大是 n=3×10^4，三者相乘最大是 3×10^4 × 3×10^4 × 3×10^4 = 2.7×10^13，超过了 int 的范围（约 2.1×10^9），也超过了无符号 int 的范围。必须用 long 来中间计算。

result = (result + (long) arr[i] * left[i] * right[i]) % MOD;
// 注意：(long) 强转在最开头，确保整个乘法用long运算

坑三：哨兵值的选择

在单次遍历版本里，用 i=n 作为哨兵触发最后的弹出，此时 curVal 需要是一个「比所有元素都小」的值，通常取 0 或 -1（因为 arr[i] >= 1）。如果取的哨兵值不够小，某些元素不会被弹出，漏计贡献。

---

七、总结

这道题的核心思想是贡献法：不从子数组的角度思考，而是从每个元素的角度出发，计算它作为最小值时贡献了多少次。

配合单调栈，可以在 O(n) 时间内高效地找到每个元素的「支配区间」（以它为最小值的所有子数组）。

记住处理重复元素的技巧：左边界严格，右边界非严格（或者反过来），确保每个子数组只被计算一次。

这个框架不只适用于子数组最小值之和，凡是涉及「所有子数组的极值统计」的问题，都可以套用。