Vault 101

xjay2007's Blog

0%

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

发表于 更新于 分类于 ，

题目描述

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

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

示例：

1
2
3
4
5
输入：[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。

提示：

  1. 1 <= A <= 30000
  2. 1 <= A[i] <= 30000

题解

单调栈

思路

  • 设置两个数组 left[] 和 right[]，left[i] 表示 A[i] 左侧第一个比它小的元素（Previous Less Element，简称 PLE）位置，right[i] 表示 A[i] 右侧第一个比它小的元素（Next Less Element，简称 NLE）位置。-1 表示左侧或右侧没有比它小的元素。
  • 通过单调栈 (Monotone Stack) 找出这两个数组。
  • 通过 A[i] 和它的 PLE 和 NLE 之间的距离，可以计算出 A[i] 在子数组中出现的次数。
  • 例
1
2
3
4
5
A[]:             [ 2,  9,  7,  8,  3,  4,  6,  1 ]
left[]:          [-1,  0,  0,  2,  0,  4,  5, -1 ]
right[]:         [ 7,  2,  4,  4,  7,  7,  7, -1 ]
leftDistance[]:  [ 0,  1,  2,  1,  4,  1,  1,  8 ]
rightDistance[]: [ 7,  2,  2,  1,  3,  2,  1,  0 ]
  • 以 3 为例
A[]:             [ 2,  9,  7,  8,  3,  4,  6,  1 ]
                   |               ^           |
               PLE of 3                     NLE of 3
                       └-----------┘
                      left distance: 4
                                   └-------┘
                                right distance: 3
  • 3 和它的 PLE 之间距离是 4，和它的 NLE 之间距离是 3。以 3 为最小元素的子数组共有 4 * 3 = 12 个。分别如下：
1
2
3
4
5
6
7
8
9
10
11
12
9, 7, 8, 3
9, 7, 8, 3, 4
9, 7, 8, 3, 4, 6
7, 8, 3
7, 8, 3, 4
7, 8, 3, 4, 6
8, 3
8, 3, 4
8, 3, 4, 6
3
3, 4
3, 4, 6
  • 子数组的和中关于 3 的和为 3 * (4 * 3)。
  • 假设 leftDistance[i] 和 rightDistance[i] 分别为 A[i] 与它的 PLE 和 NLE 之间的距离。如果 left[i] == -1 则距离为 1。
  • 由此可以计算出最终结果为 sum(A[i] * leftDistance[i] * rightDistance[i])

代码

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
var sumSubarrayMins = function(A) {
    const MOD = 1000000007;
    const len = A.length;
    let [pre_idx_stack, next_idx_stack] = [[], []];
    let [left, right] = [[], []];

    for(let i = 0; i < len; i++) {
        while(pre_idx_stack.length > 0
            && A[pre_idx_stack[pre_idx_stack.length - 1]] >= A[i]) {
                pre_idx_stack.pop();
            }
        if(pre_idx_stack.length) {
            left[i] = i - pre_idx_stack[pre_idx_stack.length - 1];
        } else {
            left[i] = i + 1;
        }
        pre_idx_stack.push(i);
    
        let j = len - i - 1;
        while(next_idx_stack.length > 0
            && A[next_idx_stack[next_idx_stack.length - 1]] > A[j]) {
                next_idx_stack.pop();
            }
        if(next_idx_stack.length) {
            right[j] = next_idx_stack[next_idx_stack.length - 1] - j;
        } else {
            right[j] = len - j;
        }
        next_idx_stack.push(j);
    }
    let sum = 0;
    for(let i = 0; i < len; i++) {
        sum += A[i] * left[i] * right[i];
        sum %= MOD;
    }
    return sum;
};

复杂度

  • 时间复杂度：$O(n)$
  • 空间复杂度：$O(n)$

暴力法

思路

  • 找出所有连续子数组中最小值，然后相加。

代码

JavaScript
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
var sumSubarrayMins = function(A) {
    const len = A.length;
    const MOD = 1000000007;
    const MAX = 30001;
    let ans = 0;
    for(let i = 0; i < len; i++) {
        let minVal = MAX;
        for(let j = i; j < len; j++) {
            if(A[j] < minVal) {
                minVal = A[j];
            }
            ans += minVal;
            and %= MOD;
        }
    }
    return ans;
};

复杂度

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(1)$

参考链接

相似文章