LeetCode 907. 子数组的最小值之和--单调栈+闭区间和开区间处理

题解：很明确可以看出来就是找某个数字A[i]作为最小值时，左边能延申位置X，右边能延申到位置Y，然后答案ans+=A[i] x (i-X+1) x (Y-i+1);这个很好理解了吧，就是找到A[i]作为最小值的区间个数，那么有个问题，比如1 2 1的数据，1和1重复了，如果按照把A[i]作为最小值处理，第一个1的左右位置就是：1和3，第3个1的左右位置就是1和3。那么答案就错了，因为两个区间相互包含了，这里的最小值是闭区间的最小值，于是我们考虑到，我们针对于左边的元素，找到的是小于等于A[i]的A[X]，右边找到的是严格大于A[i]的A[Y]。这样就可以排除区间相互包含的情况。
那么新问题来了，怎么快速找到每个A[i]的A[X]和A[Y]呢？不可能暴力找答案吧？绝对超时，于是我们想到单调栈找这个结果，O(n)的复杂度，然后顺利通过。

AC代码

class Solution {
public:
    typedef long long ll;
    stack<int>q;
    int L[30010],R[30010];
    int sumSubarrayMins(vector<int>& A) {
        ll mod=1e9+7;
        while(!q.empty())q.pop();
        int n=A.size();
        for(int i=0;i<n;i++)
        L[i]=i+1,R[i]=i+1;
        //单调栈找左边的A[X]
        for(int i=0;i<n;i++)
        {
            if(q.empty()||A[q.top()]<A[i])
            {
                q.push(i);
            }
            else
            {
                while(q.empty()==false&&A[q.top()]>=A[i])
                {
                    L[i]=L[q.top()];
                    q.pop();
                }
                q.push(i);
            }
        }
        while(!q.empty())q.pop();
        //单调栈找右边的A[Y]
        for(int i=n-1;i>=0;i--)
        {
            if(q.empty()||A[q.top()]<=A[i])
            {
                q.push(i);
            }
            else
            {
                while(q.empty()==false&&A[q.top()]>A[i])
                {
                    R[i]=R[q.top()];
                    q.pop();
                }
                q.push(i);
            }
        }
        ll ans=0;
        for(int i=0;i<n;i++)
        {
            ans+=A[i]*(i+2-L[i])*(R[i]-i);
            ans%=mod;
        }
        return ans;
    }
};