跳到主要内容

907.子数组的最小值之和

· 阅读需 2 分钟

1、题干​

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

 

示例 1：

输入：arr = [3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。

示例 2：

输入：arr = [11,81,94,43,3]
输出：444

 

提示：

  • 1 <= arr.length <= 3 * 104
  • 1 <= arr[i] <= 3 * 104

 

解题思路​

单调栈，写得有点费力

代码​

function sumSubarrayMins(arr: number[]): number {
  let res = 0;

  function dfs(c: number) {
    const n = arr[c];
    let [mins, preSum] = c < arr.length - 1 ? dfs(c + 1) : [[], 0];

    let count = 1;
    while (mins.at(-1)?.at(0) >= n) {
      const pair = mins.pop();
      count += pair[1];
      preSum -= pair[1] * pair[0];
    }

    mins.push([n, count]);
    preSum = (preSum + n * count) % (1e9 + 7);
    res = (res + preSum) % (1e9 + 7);

    return [mins, preSum];
  }

  dfs(0);

  return res;
}