907. 子数组的最小值之和

Difficulty
Medium
Tags
单调栈
URL
https://leetcode.cn/problems/sum-of-subarray-minimums/
Star
给定一个整数数组 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
通过次数17,305提交次数50,872

法1 单调栈

 
思路
基本思路：找出以A[i]为中心，且A[i]是最小值情况下，经过A[i]的subarray个数。 从A[i]出发，向左右两边寻找第一个比A[i]小的数，找到后左右范围内（exclusive）的所有subarray都是以A[i]作为最小值的。然后用数学方法算出这个范围内所有经过A[i]的subarray的个数。注意左右两数本身要被exclude。 维护一个“递增”stack。新的数不停推掉stack里比它大的数，形成i和stack[-2]两个小的数字夹住stack[-1]这一个大数字的情况。这样在(stack[-2], i)范围内（exclusive）的最小值都是stack[-1]。
题解
class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        stack = []
        arr = [0] + arr + [0]
        res = 0
        for i in range(0, len(arr)):
            while stack and arr[i] < arr[stack[-1]]:
                idx = stack.pop()
                temp = arr[idx] * (idx-stack[-1]) * (i-idx)
                res += temp
                # print(temp)
            stack.append(i)
        return res%(10**9+7)