Leetcode 943 Solution

This article provides solution to leetcode question 943 (sum-of-subarray-minimums)
Categories:
Tags:
Access this page by simply typing in "lcs 943" in your browser address bar if you have bunnylol configured.

https://leetcode.com/problems/sum-of-subarray-minimums

Solution

class Solution(object):
    def sumSubarrayMins(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        s = []
        sum_min = 0
        ans = 0

        for i, a in enumerate(A):
            j = i
            while s and s[-1][0] > a:
                sum_min -= (j - s[-1][1]) * s[-1][0]
                j = s[-1][1]
                s.pop()

            sum_min += (i - j + 1) * a
            s.append((a, j))

            ans += sum_min

        return ans % (10**9 + 7)