单调栈求区间的最小值

前缀和求区间和

class Solution {
public:
    int mintimessum(vector<int>& a) {
        int n=a.size();
        int ans=0;
        //leftmin用于存每个元素左边第一个小于本身的数的位置
        //rightmin用于存每个元素右边第一个小于本身的数的位置
        vector<int>leftmin(n);
        vector<int>rightmin(n);
        //用单调栈维护以a[i]为最小值的区间的左右端点
        stack<int>stack1;
        //区间和用前缀和求
        vector<int>pre(n+1);
        //求前缀和，注意这里的pre[1]求的就是a[0]
        for(int i=1;i<=n;i++) pre[i]=pre[i-1]+a[i-1];
        //正向遍历找到每个元素作为最小值的区间的左端点
        for(int i=0;i<n;i++){
            while(!stack1.empty()&&a[stack1.top()]>=a[i]){
                stack1.pop();  
            }
            //注意特判一下，如果这个元素的左边没有元素了，那么就将这个区间的左端点设置为-1
            leftmin[i]=stack1.empty()?-1:stack1.top();
            stack1.push(i);
        }
        //调用无参构造函数将栈清空
        stack1=stack<int>();
        //逆向遍历找右边第一个小于本身的元素的位置
        for(int i=n-1;i>=0;i--){
            while(!stack1.empty()&&a[stack1.top()]>=a[i]){
                stack1.pop();
            } 
            //特判当这个元素的右边没有元素的时候，就标记以该元素为最小值的区间的右端点为n
            rightmin[i]=stack1.empty()?n:stack1.top();
            stack1.push(i);
        }
        //遍历所有的元素，求出以某个元素为区间的最小值*区间和的最大值
        for(int i=0;i<n;i++){
            //由于是前缀和pre[1]=a[0]，所以要left+1,不包含区间右端点
            ans=max(ans,a[i]*(pre[rightmin[i]]-pre[leftmin[i]+1]));
        }
        return ans;
    }
};