题目如下：

解题思路：我的想法对于数组中任意一个元素，找出其左右两边最近的小于自己的元素。例如[1,3,2,4,5,1],元素2左边比自己小的元素是1，那么大于自己的区间就是[3]，右边的区间就是[4,5]。那么对于元素2来说，和左边区间合并组成[2,3]以及和右边区间合并组成[2,4,5]，这两段区间包括2在内的所有subarray的最小值都是2，其分别可以组成的subarry的个数是 len([3])和len([4,5]),左右区间合并在一起可以组成的subarray的个数是len([3])*len([4,5])，再加上2本身自己组成一个独立的subarray [2]，其总数就是 len([3]) + len([4,5]) + len([3])*len([4,5]) + 1,转成通项表达式就是 len(left) + len(right) + len(left)*len(right) + 1。怎么快速找到其左右两边最近的小于自己的元素？可以参考 。

代码如下：

class Solution(object):    def sumSubarrayMins(self, A):        """        :type A: List[int]        :rtype: int        """        dic = {}        for i in range(len(A)):            if A[i] not in dic:                dic[A[i]] = 0            else:                dic[A[i]] += 1                A[i] = float(str(A[i]) + '.' + '1'*dic[A[i]])        dp_left = [0] * len(A)        dp_left[0] = -1        for i in xrange(1, len(dp_left)):            j = i - 1            while A[i] <= A[j] and j != -1:                j = dp_left[j]            dp_left[i] = j        # print dp        dp_right = [0] * len(A)        dp_right[-1] = len(A)        for i in xrange(len(dp_right) - 2, -1, -1):            j = i + 1            while j != len(A) and A[i] <= A[j]:                j = dp_right[j]            dp_right[i] = j        res = 0        for i in range(len(A)):            left = i - dp_left[i] - 1            right = dp_right[i] - i - 1            A[i] = int(A[i])            res += (left*A[i] + right*A[i] + (left*right)*A[i] + A[i])                #print A[i],res        #print dp_left        #print dp_right        return res % (pow(10,9) + 7)