[leetcode] 907. Sum of Subarray Minimums

[leetcode] 907. Sum of Subarray Minimums

Description

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

Note:

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

分析

题目的意思是：求一个序列的所有连续子序列的最小值的和，这道题用暴力破解的方法肯定会超时，存在着大量的重复的操作。我尝试找规律，发现没有找到，看了答案以后，才发现原来可以把问题看成一个i长度为结尾序列的求解，i从1扩大到n就是所求了。 对于

A = [1,7,5,2,4,3,9]

[i,j]的子序列的最小值为：B = [1,2,2,2,3,3,9]， 即i=0的时候是整个数列 [1,7,5,2,4,3,9] 最小值为1,当i=1的时候，序列为[7,5,2,4,3,9]，最小值为2，依次类推就行了，这个规律我没有想到，欣赏一下，理解了这个过程就可以看代码了，代码用的是栈来实现的

代码

class Solution: def sumSubarrayMins(self, A: List[int]) -> int: MOD=10**9+7 stack=[] ans=dot=0 for j,y in enumerate(A): cnt=1 while stack and stack[-1][0]>=y: x,c=stack.pop() cnt+=c dot-=x*c stack.append([y,cnt]) dot+=y*cnt ans+=dot return ans% MOD

参考文献

​​[LeetCode] Approach 2: Maintain Stack of Minimums​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。