907. Sum of Subarray Minimums

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [3,1,2,4]
Output: 17
Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.  Sum is 17.

Note:

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

这道题给了一个数组,对于所有的子数组,找到最小值,并返回累加结果,并对一个超大数取余。由于我们只关心子数组中的最小值,所以对于数组中的任意一个数字,需要知道其是多少个子数组的最小值。就拿题目中的例子 [3,1,2,4] 来分析,开始遍历到3的时候,其本身就是一个子数组,最小值也是其本身,累加到结果 res 中,此时 res=3,然后看下个数1,是小于3的,此时新产生了两个子数组 [1] 和 [3,1],且最小值都是1,此时在结果中就累加了 2,此时 res=5。接下来的数字是2,大于之前的1,此时会新产生三个子数组,其本身单独会产生一个子数组 [2],可以先把这个2累加到结果 res 中,然后就是 [1,2] 和 [3,1,2],可以发现新产生的这两个子数组的最小值还是1,跟之前计算数字1的时候一样,可以直接将以1结尾的子数组最小值之和加起来,那么以2结尾的子数组最小值之和就是 2+2=4,此时 res=9。对于最后一个数字4,其单独产生一个子数组 [4],还会再产生三个子数组 [3,1,2,4], [1,2,4], [2,4],其并不会对子数组的最小值产生影响,所以直接加上以2结尾的子数组最小值之和,总共就是 4+4=8,最终 res=17。

分析到这里,就知道我们其实关心的是以某个数字结尾时的子数组最小值之和,可以用一个一维数组 dp,其中 dp[i] 表示以数字 A[i] 结尾的所有子数组最小值之和,将 dp[0] 初始化为 A[0],结果 res 也初始化为 A[0]。然后从第二个数字开始遍历,若大于等于前一个数字,则当前 dp[i] 赋值为 dp[i-1]+A[i],前面的分析已经解释了,当前数字 A[i] 组成了新的子数组,同时由于 A[i] 不会影响最小值,所以要把之前的最小值之和再加一遍。假如小于前一个数字,就需要向前遍历,去找到第一个小于 A[i] 的位置j,假如j小于0,表示前面所有的数字都是小于 A[i] 的,那么 A[i] 是前面 i+1 个以 A[i] 结尾的子数组的最小值,累加和为 (i+1) x A[i],若j大于等于0,则需要分成两部分累加,dp[j] + (i-j)xA[i],这个也不难理解,前面有 i-j 个以 A[i] 为结尾的子数组的最小值是 A[i],而再前面的子数组的最小值就不是 A[i] 了,但是还是需要加上一遍其本身的最小值之和,因为每个子数组末尾都加上 A[i] 均可以组成一个新的子数组,最终的结果 res 就是将 dp 数组累加起来即可,别忘了对超大数取余,参见代码如下:

解法一:

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = A[0], n = A.size(), M = 1e9 + 7;
        vector<int> dp(n);
        dp[0] = A[0];
        for (int i = 1; i < n; ++i) {
            if (A[i] >= A[i - 1]) dp[i] = dp[i - 1] + A[i];
            else {
                int j = i - 1;
                while (j >= 0 && A[i] < A[j]) --j;
                dp[i] = (j < 0) ? (i + 1) * A[i] : (dp[j] + (i - j) * A[i]);
            }
            res = (res + dp[i]) % M;
        }
        return res;
    }
};

上面的方法虽然 work,但不是很高效,原因是在向前找第一个小于当前的数字,每次都要线性遍历一遍,造成了平方级的时间复杂度。而找每个数字的前小数字或是后小数字,正是单调栈擅长的,可以参考博主之前的总结贴 LeetCode Monotonous Stack Summary 单调栈小结。这里我们用一个单调栈来保存之前一个小的数字的位置,栈里先提前放一个 -1,作用会在之后讲解。还是需要一个 dp 数组,跟上面的定义基本一样,但是为了避免数组越界,将长度初始化为 n+1,其中 dp[i] 表示以数字 A[i-1] 结尾的所有子数组最小值之和。对数组进行遍历,当栈顶元素不是 -1 且 A[i] 小于等于栈顶元素,则将栈顶元素移除。这样栈顶元素就是前面第一个比 A[i] 小的数字,此时 dp[i+1] 更新还是跟之前一样,分为两个部分,由于知道了前面第一个小于 A[i] 的数字位置,用当前位置减去栈顶元素位置再乘以 A[i],就是以 A[i] 为结尾且最小值为 A[i] 的子数组的最小值之和,而栈顶元素之前的子数组就不受 A[i] 影响了,直接将其 dp 值加上即可。将当前位置压入栈,并将 dp[i+1] 累加到结果 res,同时对超大值取余,参见代码如下:
解法二:

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = 0, n = A.size(), M = 1e9 + 7;
        stack<int> st{{-1}};
        vector<int> dp(n + 1);
        for (int i = 0; i < n; ++i) {
            while (st.top() != -1 && A[i] <= A[st.top()]) {
                st.pop();
            }
            dp[i + 1] = (dp[st.top() + 1] + (i - st.top()) * A[i]) % M;
            st.push(i);
            res = (res + dp[i + 1]) % M;
        }
        return res;
    }
};

再来看一种解法,由于对于每个数字,只要知道了其前面第一个小于其的数字位置,和后面第一个小于其的数字位置,就能知道当前数字是多少个子数组的最小值,直接相乘累加到结果 res 中即可。这里我们用两个单调栈 st_pre 和 st_next,栈里放一个数对儿,由数字和其在原数组的坐标组成。还需要两个一维数组 left 和 right,其中 left[i] 表示以 A[i] 为结束为止且 A[i] 是最小值的子数组的个数,right[i] 表示以 A[i] 为起点且 A[i] 是最小值的子数组的个数。对数组进行遍历,当 st_pre 不空,且栈顶元素大于 A[i],移除栈顶元素,这样剩下的栈顶元素就是 A[i] 左边第一个小于其的数字的位置,假如栈为空,说明左边的所有数字都小于 A[i],则 left[i] 赋值为 i+1,否则赋值为用i减去栈顶元素在原数组中的位置的值,然后将 A[i] 和i组成数对儿压入栈 st_pre。对于 right[i] 的处理也很类似,先将其初始化为 n-i,然后看若 st_next 不为空且栈顶元素大于 A[i],然后取出栈顶元素t,由于栈顶元素t是大于 A[i]的,所以 right[t.second] 就可以更新为 i-t.second,然后将 A[i] 和i组成数对儿压入栈 st_next,最后再遍历一遍原数组,将每个 A[i] x left[i] x right[i] 算出来累加起来即可,别忘了对超大数取余,参见代码如下:
解法三:

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = 0, n = A.size(), M = 1e9 + 7;
        stack<pair<int, int>> st_pre, st_next;
        vector<int> left(n), right(n);
        for (int i = 0; i < n; ++i) {
            while (!st_pre.empty() && st_pre.top().first > A[i]) {
                st_pre.pop();
            }
            left[i] = st_pre.empty() ? (i + 1) : (i - st_pre.top().second);
            st_pre.push({A[i], i});
            right[i] = n - i;
            while (!st_next.empty() && st_next.top().first > A[i]) {
                auto t = st_next.top(); st_next.pop();
                right[t.second] = i - t.second;
            }
            st_next.push({A[i], i});
        }
        for (int i = 0; i < n; ++i) {
            res = (res + A[i] * left[i] * right[i]) % M;
        }
        return res;
    }
};

我们也可以对上面的解法进行空间上的优化,只用一个单调栈,用来记录当前数字之前的第一个小的数字的位置,然后遍历每个数字,但是要多遍历一个数字,i从0遍历到n,当 i=n 时,cur 赋值为0,否则赋值为 A[i]。然后判断若栈不为空,且 cur 小于栈顶元素,则取出栈顶元素位置 idx,由于是单调栈,那么新的栈顶元素就是 A[idx] 前面第一个较小数的位置,由于此时栈可能为空,所以再去之前要判断一下,若为空,则返回 -1,否则返回栈顶元素,用 idx 减去栈顶元素就是以 A[idx] 为结尾且最小值为 A[idx] 的子数组的个数,然后用i减去 idx 就是以 A[idx] 为起始且最小值为 A[idx] 的子数组的个数,然后 A[idx] x left x right 就是 A[idx] 这个数字当子数组的最小值之和,累加到结果 res 中并对超大数取余即可,参见代码如下:
解法四:

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int res = 0, n = A.size(), M = 1e9 + 7;
        stack<int> st;
        for (int i = 0; i <= n; ++i) {
            int cur = (i == n) ? 0 : A[i];
            while (!st.empty() && cur < A[st.top()]) {
                int idx = st.top(); st.pop();
                int left = idx - (st.empty() ? -1 : st.top());
                int right = i - idx;
                res = (res + A[idx] * left * right) % M;
            }
            st.push(i);
        }
        return res;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/907

参考资料:

https://leetcode.com/problems/sum-of-subarray-minimums/

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170857/One-stack-solution

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/222895/Java-No-Stack-solution.

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/170769/Java-O(n)-monotone-stack-with-DP

https://leetcode.com/problems/sum-of-subarray-minimums/discuss/178876/stack-solution-with-very-detailed-explanation-step-by-step

LeetCode All in One 题目讲解汇总(持续更新中…)


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation