【leetcode】907. Sum of Subarray Minimums

题目如下：

解题思路：我的想法对于数组中任意一个元素，找出其左右两边最近的小于自己的元素。例如[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。怎么快速找到其左右两边最近的小于自己的元素？可以参考【leetcode】84. Largest Rectangle in Histogram 。

代码如下：

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]) + '.' + ''*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)

巴特西

【leetcode】907. Sum of Subarray Minimums

最新文章

热门文章