Method sumSubarrayMins

Array/SumOfSubarrayMinimums.py:113–185

:type A: List[int] :rtype: int

(self, A)

class Solution(object):

    def sumSubarrayMins(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        mod = 10**9 + 7
        
        # count
        left = []
        right = []

        # (num, count)
        _left = []
        _right = []
        for i in A:
            base = 1
            while _left:
                if i < _left[-1][0]:
                    base += _left[-1][1]
                    _left.pop()
                else:
                    break

            _left.append((i, base))
            left.append(base)

        for i in reversed(A):
            base = 1
            while _right:
                if i <= _right[-1][0]:
                    base += _right[-1][1]
                    _right.pop()
                else:
                    break

            _right.append((i, base))
            right.append(base)

        right.reverse()

        result = 0

        for i in range(len(A)):
            result += A[i] * left[i] * right[i] 

        return result % mod

        # result = 0
        # length = len(A)
        
        # for i in range(length):
        #     _self = 1
        #     left = 0
        #     right = 0
            
        #     for j in range(i-1, -1, -1):
        #         if A[i] < A[j]:
        #             left += 1