動機

之前有一題就是用左右兩邊的長度相乘算組合數，不過這題還要快速求出左右兩邊，所以就用了monotone stack

monotone stack有兩個用途

  • previous less element
  • next less element

詳細看這篇

Problem

Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.

 

Example 1:

Input: arr = [3,1,2,4]Output: 17Explanation: 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.

Example 2:

Input: arr = [11,81,94,43,3]Output: 444

 

Constraints:

  • 1 <= arr.length <= 3 * 104
  • 1 <= arr[i] <= 3 * 104

Sol

出左右兩邊，再一次組合起來

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        left = []
        stk = []
        for i in range(len(arr)):
            count = 1
            while stk and stk[-1][0] > arr[i]:
                num, cnt = stk.pop()
                count += cnt
            left.append(count)
            stk.append([arr[i],count])
        right = []
        stk = []
        for i in reversed(range(len(arr))):
            count = 1
            while stk and stk[-1][0] >= arr[i]:
                num, cnt = stk.pop()
                count += cnt
            right.append(count)
            stk.append([arr[i],count])
        return sum([l*a*r for l,a,r in zip(left,arr,right[::-1])]) % (10**9 + 7)

再整理stack時，可以直接算!! 因為stack下一個index就是左，現在比較大的就是右

不過要處理邊界問題，這裡用[0]+A+[0] 很神奇!!

class Solution:
    def sumSubarrayMins(self, A):
        res = 0
        s = []
        for i, x in enumerate(A):
            while s and A[s[-1]] > x:
                j = s.pop()
                k = s[-1] if s else -1
                res += A[j] * (i - j) * (j - k)
            s.append(i)
        return res % (10**9 + 7)