子数组的最小值之和

# -*- coding: utf-8 -*-

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param nums int整型一维数组
# @return int整型
#
class Solution:
    """
    题目：
        https://www.nowcoder.com/practice/a7401d0dd4ec4071a31fd434e150bcc2?tpId=196&tqId=40517&rp=1&ru=/exam/oj&qru=/exam/oj&sourceUrl=%2Fexam%2Foj%3FjudgeStatus%3D3%26page%3D1%26pageSize%3D50%26search%3D%26tab%3D%25E7%25AE%2597%25E6%25B3%2595%25E7%25AF%2587%26topicId%3D196&difficulty=undefined&judgeStatus=3&tags=&title=
    参考：
        https://leetcode.cn/problems/sum-of-subarray-minimums/solution/zi-shu-zu-de-zui-xiao-zhi-zhi-he-by-leetcode/
    算法：
        对于每个 j，考虑所有子序列 [i, j] 的最小值。想法是每当我们增加 j，这些最小值可能会有关联，事实上，min(A[i:j+1]) = min(A[i:j], A[j+1])。
        我们维护最小值栈stack，stack中存储的元素为(x, c)，表示以x为结尾且x为最小值的区间个数，stack按照x单调递增。枚举区间右端点j，弹出栈中 x >= y的元素，因为这些以x结尾且以x为最小值的区间，尾部追加y之后，变成以y结尾且以y为最小值的区间了。另外我们使用Sum来记录以当前元素y结尾的所有区间的最小值之和。
    复杂度：
        时间复杂度：O(n)
        空间复杂度：O(n)
    """

    def sumSubarr(self, nums):
        # write code here
        MOD = 10 ** 9 + 7
        ans, Sum, stack = 0, 0, []

        for j, y in enumerate(nums):
            count = 1
            while stack and stack[-1][0] >= y:
                x, c = stack.pop() # 以元素x结尾的区间个数为c，现在我们将元素y作为这些区间的尾部，也就是之前c个以元素x为最小值的区间 变为 以元素y作为最小值的区间
                count += c
                Sum -= x * c # dot始终记录以当前元素y结尾的所有区间的最小值之和
            stack.append((y, count)) # count表示以元素y结尾且y作为区间最小值的区间个数
            Sum += y * count
            ans += Sum # 累加以y结尾的所有区间的最小值之和

        return ans % MOD

if __name__ == "__main__":
    sol = Solution()

    # nums = [3, 1, 2, 4, 5]

    # nums = [3, 1, 2, 4]

    # nums = [11, 81, 94, 43, 3]

    nums = [1, 2]

    # nums = [3, 2, 1]

    res = sol.sumSubarr(nums)

    print res