Skip to content

Latest commit

 

History

History
163 lines (99 loc) · 4.48 KB

0907._Sum_of_Subarray_Minimums.md

File metadata and controls

163 lines (99 loc) · 4.48 KB
Raw

907. Sum of Subarray Minimums

难度: Medium

刷题内容

原题连接

内容描述


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

解题方案

思路 1 - 时间复杂度: O(N)- 空间复杂度: O(N)******

对于A中的每一个元素，我们只需要计算出以它为最小值且以它为结束的子串的个数left[i]，然后再计算出以它为最小值且以它为开始的子串的个数right[i]， 注意这其中不允许有重复（即一个优先原则，例如1,2,3,1，其中先出现的那个1才是最小值，这样可以避免我们重复计算子串）

然后假设我们的A为[3,2,1,2,3]

那么对于中间的1来说，它的left[i]为3，right[i]也为3
那么它一共涉及到多少个字串呢，我们枚举一下

3,2,1
2,1
1
3,2,1,2
2,1,2
1,2
3,2,1,2,3
2,1,2,3
1,2,3


一共涉及到9个，也就是说以A{i]为最小值的子串总数其实等于left[i] 和right[i]的乘积，这个也可以自己想出来，枚举只是为了看的更清晰

所以现在我们的目标变成了求以A中每一个元素为最小值的子串个数的list，命名为sub_counts

例如还是上面的例子，我们的sub_counts = [11, 21, 33, 12, 1*1], 这里的对称性不是普遍的，因为我们的输入是对称的。

所以我们的结果就是A中的每一个元素与其sub_count乘积的总和，即3*(11) + 2(21) + 1(33) + 2(12) + 3(1*1) = 23

整个思路都是参考寒神的

AC 代码如下: beats 53.98%

class Solution(object):
    def sumSubarrayMins(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        stack_left, stack_right = [], []
        # 分别代表左边和右边所涉及的子串个数的list
        sub_left, sub_right = [0] * len(A), [0] * len(A)
        for i in range(len(A)):
            count = 1 # 初始都是1，因为自己本身算一个
            while stack_left and stack_left[-1][0] > A[i]:
                count += stack_left.pop()[1]
            sub_left[i] = count # 其左边涉及子串个数为count
            # stack—_left里面存的是A[i]这个元素前面有多少个严格比它小的数字
            stack_left.append((A[i], count)) 
        for i in range(len(A))[::-1]:
            count = 1 
            while stack_right and stack_right[-1][0] >= A[i]:
                count += stack_right.pop()[1]
            sub_right[i] = count # 其右边涉及子串个数为count
            # stack—_right里面存的是A[i]这个元素前面有多少个大于等于它的数字
            stack_right.append((A[i], count))
        
        return sum(a * l * r for a, l, r in zip(A, sub_left, sub_right)) % (10**9 + 7)

时间复杂度为O(N)，因为对于A中的每一个元素我们都值进行了恰好两次push stack操作和最多2次pop stack的操作，因此是O(N)

空间显然为O(N)

思路 2 - 时间复杂度: O(N)- 空间复杂度: O(N)******

看了下，别人说这两个stack可以one pass，一个stack就够了, beats 100%

不得不说，其中left = stack[-1] if stack else -1这句代码真的精妙绝伦，至少我想不到 代码如下：

class Solution(object):
    def sumSubarrayMins(self, A):
        """
        :type A: List[int]
        :rtype: int
        """
        count, stack = 0, []
        for i in range(len(A)):
            while stack and A[stack[-1]] >= A[i]:
                pos = stack.pop()
                # 下面这句代码是整个代码中最精妙的一句了
                left = stack[-1] if stack else -1
                # 这里一次就把涉及A[i]的子串的和全部加上次
                count += (i - pos) * (pos - left) * A[pos]
            stack.append(i)
            
        while stack:
            pos = stack.pop()
            left = stack[-1] if stack else -1
            count += (pos - left) * (len(A) - pos) * A[pos]
        return count % (10**9 + 7)