[数据结构与算法]LeetCode每日一题——907. 子数组的最小值之和

LeetCode每日一题系列

题目：907. 子数组的最小值之和
难度：普通

题目

给定一个整数数组 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

思路

题目简而言之就是求给定数组的子数组的所有子数组中最小元素的和。
该问题我们可以转换为单调栈的问题，

• 我们需要找到每个元素 arr[i] 以该元素为最右且最小的子序列的数目 left[i]，以及以该元素为最左且最小的子序列的数目 right[i]，则以 arr[i] 为最小元素的子序列的数目合计为 left[i]×right[i]
• 只需要求出数组中当前元素 x（下标i） 左边第一个小于 x 的元素(下标j)以及右边第一个小于等于 x 的元素(下标k)
• 则以为arr[i]为最小元素对答案的贡献就是arr[i] * (i-j) * (k-i)，最后整合所有元素即可

题解

MOD = 10 ** 9 + 7

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        n = len(arr)
        monoStack = []
        # arr[i]左右两边小于该元素的元素数量和
        left = [0] * n
        right = [0] * n
        # 寻找左边
        for i, x in enumerate(arr):
            while monoStack and x <= arr[monoStack[-1]]:
                monoStack.pop()
            left[i] = i - (monoStack[-1] if monoStack else -1)
            monoStack.append(i)
        monoStack = []
        # 寻找右边
        for i in range(n - 1, -1, -1):
            while monoStack and arr[i] < arr[monoStack[-1]]:
                monoStack.pop()
            right[i] = (monoStack[-1] if monoStack else n) - i
            monoStack.append(i)
        ans = 0
        # 整合答案
        for l, r, x in zip(left, right, arr):
            ans = (ans + l * r * x) % MOD
        return ans