907. Sum of Subarray Minimums - cocoder39/coco39_LC GitHub Wiki

907. Sum of Subarray Minimums

brute force: build sublist and maintain the min within the sublist, O(N^2) for nested loop

new idea: * for each element, find the number of sublists where this element is min within the sublist * mono increasing stack to get left bound and right bound of an element. stack[-1] < arr[i] means i is the bound of stack[-1] * stack[-1][1] > arr[i] or stack[-1][1] >= arr[i] works. they will result in same final value * count = (idx-left_bound) * (i-idx): because left could be empty and right could be empty

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD = 10**9 + 7
        stack = []
        total = 0
        N = len(arr)
        for i in range(N+1):
            while stack and (i == N or stack[-1][1] > arr[i]):
                idx, min_val = stack.pop()
                left_bound = -1 if not stack else stack[-1][0]
                count = (idx-left_bound) * (i-idx)
                print(min_val, left_bound, idx, i)
                total += count * min_val
                total %= MOD
            if i < N:
                stack.append((i, arr[i]))
        return total