Q907 Sum of Subarray Minimums

Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [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.

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000

解题思路：

对于列表中的每一个数字，计算比该数字大的最远左边界与最远右边界。例如，[3,1,2,4]，对于1来说，它的最远左边界是3，最远右边界是4。因此，子数组中最小值结果为1的共有 2*3=6 个子数组（从1到3的距离为2，从1到4的距离为3）。

事实上，我们可以得出这样一个数学规律：最小子数组之和等于当前数字的最远左间隔与当前数字的最远右间隔的乘积，然后再乘以当前数字，最后把所有和累积起来。

采用传统的方法，时间复杂度为 O(n^2)，会超时，见Python实现部分。

改进方法：可以使用两个单调栈，分别保存从左到右的左边界下标和从右到左的右边界下标。得到的这些左边界下标和右边界下标都用长度为n的列表保存起来，最后再使用一个for循环输出结果。时间复杂度会降低，空间复杂度为O(n)，见Python实现2部分。举例如下：

[3,1,2,4]
从左到右，左边界为 1 2 1 1
从右到左，右边界为 1 3 2 1 （做法：将列表反转，找左边界）
结果： (1*1) * 3 + (2*3) * 1 + (1*2) *2 + (1*1) * 4 = 17。

Python实现：

class Solution:
    # 时间复杂度：O(n^2) ，超时
    def sumSubarrayMins(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        lens = len(A)
        totsum = 0
        for ind, tar in enumerate(A):
            left, right = ind - 1, ind + 1
            while left >= 0 and tar < A[left]:
                left -= 1
            while right < lens and tar <= A[right]:
                right += 1
            totsum += ((ind - left) * (right - ind)) * tar
        return totsum % (10 ** 9 + 7)

Python实现2：

    # 空间复杂度：O(n)，AC
    def sumSubarrayMins2(self, A):
        N = len(A)
        # 单调栈求出所有的左序
        stack = []
        prev = [None] * N
        for i in range(N):
            while stack and A[i] <= A[stack[-1]]:
                stack.pop()
            prev[i] = stack[-1] if stack else -1
            stack.append(i)
        # 单调栈求出所有的右序
        stack = []
        next_ = [None] * N
        for k in range(N-1, -1, -1):
            while stack and A[k] < A[stack[-1]]:
                stack.pop()
            next_[k] = stack[-1] if stack else N
            stack.append(k)
        # 求结果
        return sum((i - prev[i]) * (next_[i] - i) * A[i] for i in range(N)) % (10**9 + 7)

A = [3,1,2,4]
B = [71,55,82,55]
C = [81,55,2]
print(Solution().sumSubarrayMins2(A)) # 17
print(Solution().sumSubarrayMins2(B)) # 593
print(Solution().sumSubarrayMins2(C)) # 197