欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 907 - 子数组的最小值之和

程序员文章站 2022-07-15 16:33:53
...

题目描述

907. 子数组的最小值之和

解法:单调栈(C++)

详细参考 官方题解

  • 利用单调栈记录截止到当前下标之前的所有下边界
  • 利用sum[i]sum[i]记录所有以ii为终点的区间最小值之和

我们将栈中大于等于A[i]A[i]的元素全部弹出,这时,如果栈空,即说明在数组中从首元素到A[i]A[i]是递减的(非严格递减),于是,那么就存在i+1i+1个子数组的最小值为A[i]A[i],为什么呢?

LeetCode 907 - 子数组的最小值之和

如果栈不空的话,即说明A[i]A[i]仅是某一段子数组的最小值,那么这个时候的和为多少呢?还记的我们的sum[...]sum[...]数组吗,对啦,这时栈顶所记录的下标对应的元素之前的最小值之和就是sum[st.top()]sum[st.top()],所以这时到A[i]A[i]为止的最小值之和就为sum[st.top()]+A[i](ist.top())sum[st.top()]+A[i]*(i-st.top()),至于ist.top()i-st.top()其实就和上面那张图解释的是一样

class Solution {
public:
    int sumSubarrayMins(vector<int>& A) {
        const long MOD = 1e9+7;
        int n = A.size();
        stack<int> st;
        vector<long> sum(n, 0);
        for(int i=0;i<n;i++)
        {
            while(!st.empty() && A[st.top()]>=A[i])
                st.pop();
            if(st.empty()) sum[i] = A[i]*(i+1);
            else sum[i] = sum[st.top()]+A[i]*(i-st.top());
            sum[i] %= MOD;
            st.push(i);
        }
        long res = 0;
        for(auto x: sum)
        {
            res += x;
            res %= MOD;
        }
        return res;
    }
};
相关标签: 题解