#907. 子数组的最小值之和

LeetCode 原题链接

#题目描述

给定一个整数数组 arr，找到每个连续子数组中的最小值，并返回这些最小值之和。答案可能很大，需要对 10⁹ + 7 取模。

输入：arr = [3, 1, 2, 4]
输出：17

所有连续子数组及其最小值为：

最小值之和为 3 + 1 + 2 + 4 + 1 + 1 + 2 + 1 + 1 + 1 = 17。

#从枚举子数组到计算贡献

暴力做法会枚举每个子数组，再寻找其中的最小值，时间复杂度至少为 O(n²)。

换一个角度：不再逐个考察子数组，而是计算每个元素作为最小值时，能出现在多少个子数组中。

答案 = Σ arr[i] × arr[i] 作为最小值的子数组数量

对于 arr[i]，如果能够找到：

• 左边第一个严格小于 arr[i] 的位置 left；
• 右边第一个小于或等于 arr[i] 的位置 right；

那么以 arr[i] 为最小值的子数组必须：

• 从 [left + 1, i] 中选择起点，共有 i - left 种选择；
• 从 [i, right - 1] 中选择终点，共有 right - i 种选择。

因此 arr[i] 的贡献是：

arr[i] × (i - left) × (right - i)

#示例：元素 1 的贡献

在 arr = [3, 1, 2, 4] 中，考察下标 1 的元素 1：

下标：       -1   0   1   2   3   4
元素：       边界  3  [1]  2   4  边界
                  ← 起点   终点 →

• 左边没有更小元素，所以 left = -1。
• 右边没有小于或等于 1 的元素，所以 right = 4。
• 起点有 1 - (-1) = 2 种选择：下标 0 或 1。
• 终点有 4 - 1 = 3 种选择：下标 1、2 或 3。

所以元素 1 是 2 × 3 = 6 个子数组的最小值，贡献为：

1 × 2 × 3 = 6

#为什么使用单调栈？

对每个元素分别向左右扫描寻找更小元素，最坏需要 O(n²) 时间。

单调递增栈可以保存“右边界还没有确定”的元素下标。当遇到一个小于或等于栈顶元素的值时：

• 当前下标就是栈顶元素的右边界；
• 栈顶弹出后，新的栈顶就是它的左边界；
• 两侧边界都已确定，可以立即计算贡献。

栈中保存下标而不是数值，因为计算左右可选数量时需要使用下标距离。

#重复元素如何处理？

例如 arr = [2, 2]，整个子数组 [2, 2] 的最小值只能计算一次。

本文统一使用：

• 左边寻找严格小于当前元素的位置；
• 右边寻找小于或等于当前元素的位置。

也就是遇到相等元素时弹栈，把包含两个 2 的子数组归给右边的 2。一边严格、一边允许相等，可以避免重复计算。

也可以反过来规定“左边小于或等于、右边严格小于”，但两边不能同时使用相同的严格规则。

#JavaScript 实现

var sumSubarrayMins = function (arr) {
  const MOD = 1_000_000_007;

  // 栈中保存下标，并保持对应元素严格递增
  // -1 是左侧虚拟边界，方便统一计算距离
  const stack = [-1];
  let result = 0;

  // 多遍历一轮，最后用 -Infinity 清空栈中剩余元素
  for (let right = 0; right <= arr.length; right++) {
    const current = right < arr.length ? arr[right] : -Infinity;

    // 当前元素小于或等于栈顶元素时，栈顶元素的右边界确定
    while (
      stack[stack.length - 1] !== -1 &&
      arr[stack[stack.length - 1]] >= current
    ) {
      const index = stack.pop();
      const left = stack[stack.length - 1];

      const startChoices = index - left;
      const endChoices = right - index;
      const contribution = arr[index] * startChoices * endChoices;

      result = (result + contribution) % MOD;
    }

    stack.push(right);
  }

  return result;
};

最后一轮的 current = -Infinity 是一个虚拟的极小值，只用于弹出栈内剩余元素。虽然它对应的下标会被压栈，但循环随即结束，因此不会参与计算。

#执行过程

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

总和为 3 + 4 + 4 + 6 = 17。

#正确性说明

栈始终保持对应元素严格递增。某个下标 index 被弹出时：

• 新栈顶 left 是左边第一个严格小于 arr[index] 的位置；
• 触发弹栈的 right 是右边第一个小于或等于 arr[index] 的位置。

所以在 left 与 right 之间，所有包含 index 的合法子数组都以 arr[index] 为最小值，其数量正好是：

(index - left) × (right - index)

一边严格、一边允许相等的边界规则还保证了含重复最小值的子数组只归属于其中一个元素。因此所有子数组都会被统计一次，并且不会重复。

#复杂度分析

• 时间复杂度：O(n)。每个下标最多入栈一次、出栈一次。
• 空间复杂度：O(n)。最坏情况下数组严格递增，所有下标都会留在栈中。

#易错点

• 栈中保存了元素值，导致无法计算左右距离；这里应保存下标。
• 忘记处理遍历结束后仍在栈中的元素，可以追加虚拟极小值统一结算。
• 重复元素的两侧边界都使用严格小于，导致重复计算。
• 贡献公式写错。起点选择数是 index - left，终点选择数是 right - index。
• 忘记对答案取模。
• 把单调栈理解成只在数组单调时才能使用。它的作用正是在线性时间内寻找每个元素附近第一个更大或更小的元素。

#面试时怎么说

把问题转换为计算每个元素作为子数组最小值的贡献。用单调递增栈找到它左边第一个严格更小的位置和右边第一个小于或等于它的位置。如果两侧边界分别是 left、right，那么起点有 i - left 种选择，终点有 right - i 种选择，贡献为 arr[i] × (i - left) × (right - i)。每个下标只入栈、出栈一次，所以时间复杂度为 O(n)。

#自测

1. 为什么贡献公式中要把左右选择数量相乘？
2. 为什么栈中必须保存下标？
3. 为什么遇到相等元素时也要弹栈？
4. 最后的虚拟极小值有什么作用？