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:
分析：
首先还是先强调一点，看到这种mod1e9+7的题目，首先要想到的就是dp！
那么我们怎样定义dp[i]呢？因为我以前见到过这种题目，所以我知道定义dp[i]为以nums[i]最小的子串的个数，说实话可能对于第一次见的人直接想到这样定义有点难度。
如[3,1,2,4]对于“1”来说，子串有[1],[3,1],[1,2],[3,1,2],[1,2,4],[3,1,2,4]，所以dp[1] = 6.
那么再来思考第二个问题，如何去计算dp[i]呢
也就是说，我们对于每个A[i]，要分别找到左边和右边第一个比他小的点，以此来确定以A[i]为最小的最长子串
例如对于[3,1,4,2,5,3,3,1]中的“2”，我们找到的串就为[4,2,5,3,3]，2左边有1个数，2右边有3个数，所以2作为最小值的串有2*4=8种。读者可以自己检验一下
那又有一个新的问题，如何对每一个点都找到其左边和右边第一个比他小的点呢？
这就要用到stack了，这部分逻辑用文字描述可能有点难度，还是看下面这段代码吧1
2
3
4
5
6
7
8
9
10
11
12
13
14
15# 找到每个点左边的第一个比该点小的位置，若无则用-1表示
def getIndex(A):
stack = [0]
left = [-1] * len(A)
for i in range(1,len(A)):
if A[i] > A[stack[-1]]:
left[i] = stack[-1]
else:
while stack and A[i] <= A[stack[-1]]: stack.pop()
if not stack: left[i] = -1
else: left[i] = stack[-1]
stack.append(i)
return left
# example [3,1,2,4]
# getIndex(A) = [-1,-1,1,2]
弄明白这两点之后这道题便可解了1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30class Solution(object):
def sumSubarrayMins(self, A):
mod = 10**9 + 7
left = [-1] * len(A)
right = [len(A)] * len(A)
# 计算left数组
stack = [0]
for i in range(1,len(A)):
if A[i] > A[stack[-1]]:
left[i] = stack[-1]
else:
while stack and A[i] <= A[stack[-1]]: stack.pop()
if not stack: left[i] = -1
else: left[i] = stack[-1]
stack.append(i)
# 计算right数组
stack = [len(A)-1]
for i in range(len(A)-2,-1,-1):
if A[i] > A[stack[-1]]:
right[i] = stack[-1]
else:
while stack and A[i] < A[stack[-1]]: stack.pop()
if not stack: right[i] = len(A)
else: right[i] = stack[-1]
stack.append(i)
res = 0
for i in range(len(A)):
res += A[i] * (i-left[i]) * (right[i]-i)
return res % mod