907.子数组的最小值之和

【LetMeFly】907.子数组的最小值之和：单调栈

力扣题目链接：https://leetcode.cn/problems/sum-of-subarray-minimums/

给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。

由于答案可能很大，因此 返回答案模 10^9 + 7 。

 

示例 1：

输入：arr = [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。

示例 2：

输入：arr = [11,81,94,43,3]
输出：444

 

提示：

• 1 <= arr.length <= 3 * 104
• 1 <= arr[i] <= 3 * 104

 

方法一：单调栈

要求的是： 每个元素 ✖ 这个元素及左边数个元素的个数 ✖ 这个元素及右边数个元素的个数。

左边右边到哪里为止呢？到小于这个元素的元素位置的前一个位置。

好了，怎么确定左右两边小于这个元素的位置呢？使用一个单调递增的单调栈即可。

栈中存放数组的下标，保证每个下标在数组中对应的元素是单调递增的。

遍历数组，当当前元素小于栈顶元素时，不断将栈顶元素弹出。诶，被弹出的这个元素的“左右到达位置不就确定了吗？”

被弹出元素右边到达的位置即为当前元素的前一个元素，被弹出元素左边到达的位置即为这个元素在栈中的下一个元素（不包含）。

为了方便，可以在初始时将栈顶入栈一个-1并在数组末尾加一个元素-1作为哨兵。期间注意不要超过32位整数。

• 时间复杂度$O(len(nums))$
• 空间复杂度$O(len(nums))$

AC代码

C++

const int MOD = 1e9 + 7;
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        arr.push_back(-1);
        stack<int> st;
        st.push(-1);
        long long ans = 0;
        for (int i = 0; i < arr.size(); i++) {
            while (st.size() > 1 && arr[i] < arr[st.top()]) {
                int last = st.top();
                st.pop();
                ans = (ans + (long long)arr[last] * (last - st.top()) * (i - last)) % MOD;
            }
            st.push(i);
        }
        return ans;
    }
};

Python

# from typing import List

MOD = 1000000007
class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        st = [-1]
        arr.append(-1)
        ans = 0
        for i in range(len(arr)):
            while len(st) > 1 and arr[i] < arr[st[-1]]:
                last = st.pop()
                ans = (ans + arr[last] * (last - st[-1]) * (i - last)) % MOD
            st.append(i)
        return ans

同步发文于CSDN，原创不易，转载经作者同意后请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/134652093