Skip to content

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

作者:Choi Yang
更新于:7 个月前
字数统计:1.3k 字
阅读时长:5 分钟

题目描述

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

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

示例:

javascript
输入:[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]。
最小值为 3124112111,和为 17

提示:

javascript
1 <= A <= 30000;
1 <= A[i] <= 30000;

来源:力扣(LeetCode)链接:https://leetcode-cn.com/problems/sum-of-subarray-minimums 著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。

解题思路

搬运 jack-108大佬的题解

既然是求子数组中最小值的和,就是求 以 A[i] 作为最小数能构成的数组有多少个。

比如 [2,4,1,2] ,以1 为最小数。能构成的数组数为 (2+1)*(1+1)2 表示 1 左面有两个比它大的数,1 表示 1 右面有一个比它大的数。

用单调栈求出 A[i] 对应的左右最近比 A[i] 小的数,记索引为 prev,next,A[i] 为最小数能形成的数组为

javascript
(i - prev[i]) * (next[i] - i);

这里为什么没有加 1 了呢,因为 prev[i]已经是比 A[i] 小的数了,能和 A[i] 形成数组的都是比 A[i] 大的数。

我的解题方式:

注释已经足够详细,还是补充一下,我参考了大佬的解题代码,只不过我是直接求出来了以当前 A[i] 为最小值的子数组左右两边 大于或等于当前值的个数。这样后续求和直接相乘即可。(不过这里要强调一下,如果左边设置大于等于了,右边就只能是大于了,不然会重复计算相等的值)

开始有点看不懂大佬为啥左边初始化为 -1,右边初始化为 A.length 。假如我们遇到了这种情况,左边都比当前 A[i] 要大,那我们维护的单调递减栈就会不断出栈,不断出栈,直到栈为空为止,此时左边个数应该为 i+1(从 0 开始计数嘛),那么这部分大佬设为 -1 就很巧妙了,问题也就自然明白啦,个人感觉自己写的还是比较好理解一点,不然直接弄一个 -1 ,第一次用单调栈,还是不太熟...

那么对于右边初始化为 A.length ,也是同理啦,当右边都比当前 A[i] 要大,那我们维护的单调递减栈就会不断出栈,不断出栈,直到栈为空为止,此时右边个数应该为 A.length-i(不用+1的原因是从 0 计数),那么这部分大佬设为 A.length 就很巧妙了,依旧清晰明了。

javascript
/**
 * @param {number[]} A
 * @return {number}
 */
var sumSubarrayMins = function (A) {
  let mod = 1e9 + 7;
  // 维护一个栈
  let stack = [];
  // 求以A[i]为最小值的子数组左边大于或等于自己的个数
  let prev = [];
  for (let i = 0; i < A.length; i++) {
    while (stack.length && A[stack[stack.length - 1]] >= A[i]) stack.pop();
    // 如果栈为空,即左边都比自己大,则返回i+1,否则返回i-栈顶元素(即保存的下标值)
    prev[i] = stack.length ? i - stack[stack.length - 1] : i + 1;
    stack.push(i);
  }
  stack = [];
  // 求以A[i]为最小值的子数组右边大于自己的个数(没有等号是因为不会重复计算相等的值)
  let nextv = [];
  for (let i = A.length - 1; i >= 0; i--) {
    while (stack.length && A[stack[stack.length - 1]] > A[i]) stack.pop();
    // 如果栈为空,即右边都比自己大,则返回A.length-i,否则返回栈顶元素(即保存的下标值)-i
    nextv[i] = stack.length ? stack[stack.length - 1] - i : A.length - i;
    stack.push(i);
  }
  let sum = 0;
  for (let i = 0; i < A.length; i++) {
    // 以A[i] 为最小值的子数组的组合共有prev[i]*nextv[i]种情况,那么和的话乘以A[i]累加即可
    sum += prev[i] * nextv[i] * A[i];
    // 按题意,进行取模运算
    sum %= mod;
  }
  return sum;
};
cpp
class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int mod = 1e9 + 7;
        stack<int> st;
        vector<int> prev(A.size()), next(A.size());
        for (int i = 0; i < A.size(); i++) {
            while (!st.empty() && A[st.top()] >= A[i]) st.pop();
            prev[i] = st.empty() ? i + 1 : i - st.top();
            st.push(i);
        }
        while (!st.empty()) st.pop();
        for (int i = A.size() - 1; i >= 0; i--) {
            while (!st.empty() && A[st.top()] > A[i]) st.pop();
            next[i] = st.empty() ? A.size() - i : st.top() - i;
            st.push(i);
        }
        int sum = 0;
        for (int i = 0; i < A.size(); i++) {
            sum += prev[i] * next[i] * A[i];
            sum %= mod;
        }
        return sum;
    }
};
java
class Solution {
    public int sumSubarrayMins(int[] A) {
        int mod = 1_000_000_007;
        Stack<Integer> st = new Stack<>();
        int[] prev = new int[A.length];
        for (int i = 0; i < A.length; i++) {
            while (!st.isEmpty() && A[st.peek()] >= A[i]) st.pop();
            prev[i] = st.isEmpty() ? i + 1 : i - st.peek();
            st.push(i);
        }
        while (!st.isEmpty()) st.pop();
        int[] next = new int[A.length];
        for (int i = A.length - 1; i >= 0; i--) {
            while (!st.isEmpty() && A[st.peek()] > A[i]) st.pop();
            next[i] = st.isEmpty() ? A.length - i : st.peek() - i;
            st.push(i);
        }
        int sum = 0;
        for (int i = 0; i < A.length; i++) {
            sum += prev[i] * next[i] * A[i];
            sum %= mod;
        }
        return sum;
    }
}
python
class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        mod = 10 ** 9 + 7
        stack = []
        prev = [0] * len(A)
        for i in range(len(A)):
            while stack and A[stack[-1]] >= A[i]:
                stack.pop()
            prev[i] = i + 1 if not stack else i - stack[-1]
            stack.append(i)
        stack = []
        nextv = [0] * len(A)
        for i in range(len(A) - 1, -1, -1):
            while stack and A[stack[-1]] > A[i]:
                stack.pop()
            nextv[i] = len(A) - i if not stack else stack[-1] - i
            stack.append(i)
        res = 0
        for i in range(len(A)):
            res += prev[i] * nextv[i] * A[i]
            res %= mod
        return res
javascript
学如逆水行舟,不进则退

Contributors

Choi Yang