子数组的最小值之和--单调栈的思想

0x01.问题

给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。

示例：
输入：[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。

C++函数形式为    int sumSubarrayMins(vector<int>& A)

0x02.问题分析

首先第一个要弄懂的是，什么是子数组？从题中的输入示例可以看出，子数组应该满足以下条件

• 在数组中，按照从左到右顺序排列的，包含数组的连续元素的小数组。
• 元素个数不限，可以为1，也可以为数组本身。

再来看一下我们需要求的是什么？

• 所有子数组的最小值之和。

涉及到所有的子数组，所以我们首先要将这个抽象的子数组具体表示出来。

• 我们假设数组是 [1]，那么子数组就是[1]。
• 假设数组是[1,2]，那么子数组就是[1],[1,2],[2]。
• 假设数组是[1,2,5]，那么子数组就是[1],[1,2],[2],[1,2,5],[2,5],[5]。
• 怎么样，发现规律了嘛？不妨我们再来写一组。
• 假设数组是[1,2,5,3]。那么子数组是[1],[1,2],[2],[1,2,5],[2,5],[5],[1,2,5,3],[2,5,3],[5,3],[3]。
• 没错，对于大小为j的数组，它的子数组就是j-1的子数组，加上[i,j]构成的数组，其中0=<i<=j。

把子数组表示出来以后，我们就要开始找最小值了。

先用动态的思想假设一下，假设A[j-1]的子数组最小值已经求出了，那么怎么来求A[j]的子数组最小值之和呢？

对于A[j]来说，A[j]与A[j-1]的区别仅在于第j号元素，也就是说要计算A[j]的子数组最小值之和，只要计算出[i,j]的最小值之和就好了，但是当我们把这个j号元素加上之后，并无法得出[i,j]这个子数组的最小值，我们当然不可能每加上一个元素，就找出每个子序列的最小值，这是不现实的，既然不能直接得到最小值，那么我们可以转换一下思路，如果我们知道加入的这个元素会对前面多少个子数组产生影响，那问题同样可以轻松解决。

我们可以维护一个单调栈，记录到目前为止的最靠近的最小值，这个单调栈应该满足下列条件

• 若栈为空，元素直接入栈。
• 若新元素大于栈顶元素，直接入栈。
• 若新元素小于栈顶元素，不断的pop，直到栈顶元素小于新元素。
• 栈元素的第一个值为[i,j]的最靠近j的最小值。
• 栈元素的第二个值为当前元素之前有多少个值大于等于这个元素（包含这个元素，所以初始值为1）。

我们的思路是：

• 设置一个变量ans来记录最终的答案。
• 设置一个变量tmp来记录每次产生的影响。
• 如果栈的一个元素出栈，那么tmp应该减去相应的值，因为这个时候，已经不是那个值构成最小值了，并且新元素的count应该加1。

0x03.最终解决代码（单调栈）

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        int ans=0,tmp=0,i;
        int MOD=1e9+7;
        stack<pair<int,int>> s;
        for(i=0;i<A.size();i++){
            int count=1;
            while(!s.empty()&&s.top().first>=A[i]){
                auto top=s.top();
                s.pop();
                count+=top.second;
                tmp-=top.first*top.second;
            }
            s.push(make_pair(A[i],count));
            tmp+=A[i]*count;
            ans+=tmp;
            ans%=MOD;
        }
        return ans;
    }
};

ATFWUS --Writing By 2020–03–19