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;
    }
};

猜你喜欢