# 907. Sum of Subarray Minimums

# 10 / 8

- Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr.

Input: arr = [3,1,2,4]
Output: 17
Explanation: 
Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. 
Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1.
Sum is 17.

1. generate all possibilties of Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4].
2. find each min(v)

[-inf, 3, 1, -inf]
--
monotonic stack []
[3,1] -> [3,1] ,[3], [1]

n = 3
stack[3]

n = 1
stack[(3, 0)] (1, 1)

0-0 -> min() -> 3

stack[(1, 1)]

0-1 -> min() -> 1

class Solution(object):
    def sumSubarrayMins(self, arr):
        
        # step 1 init
        arr = [-inf] + arr + [-inf]
        monoIdxStack = []
        ans = 0
        
        # [   0, 1, 2,    3] idx
        # [-inf, 1, 1, -inf] val
        # step 2 process n
        for idx, num in eunmerate(arr):
            # idx = 2 num = 1
            # monoIdxStack = [0, 1]
            while monoIdxStack and arr[monoIdxStack[-1]] > num:
                preIdx = monoIdxStack.pop() # 1 -> idx of 3
                left = monoIdxStack[-1]
                right = idx
                
                l = (preIdx - left)  # 1 - 0
                r = (right - preIdx) # 2 - 1
                
                # amortized
                
                # (2 - 0 - 1) * 3 for range [1-1]
                # right = 2
                # left = 0

                # sum of this num as a minimal val in range(left, right)
                s = l*r*arr[preIdx]
                ans += s
                
            monoIdxStack.append(idx)
           
        # step 3 ans
        return ans