907.md

[907] Sum of Subarray Minimums

Description

link

---

Solution

• See Code

---

Code

O(n)

class Solution:
    def sumSubarrayMins(self, A: List[int]) -> int:
        # The times a number n occurs in the minimums is |left_bounday-indexof(n)| * |right_bounday-indexof(n)| 
        # The total sum is sum([n * |left_bounday - indexof(n)| * |right_bounday - indexof(n)| for n in array]
        res = 0
        stack = []  #  non-decreasing 
        A = [float('-inf')] + A + [float('-inf')]
        for i, n in enumerate(A):
            # stack[-1], i is the left and right bounday
            while stack and A[stack[-1]] > n:
                cur = stack.pop()
                res += A[cur] * (i - cur) * (cur - stack[-1]) 
            stack.append(i)
        return res % (10**9 + 7)