Given an array of integers arr, find the sum of min(b)
, where b
ranges over every (contiguous) subarray of arr
. Since the answer may be large, return the answer modulo 109 + 7
.
Example 1:
Input: arr = [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.
Example 2:
Input: arr = [11,81,94,43,3]
Output: 444
Constraints:
1 <= arr.length <= 3 104
1 <= arr[i] <= 3 104
题目大意:
求所有子数组的最小值的和
算法思路:
求区间最值用Stack,因为是最小值,所以用递增栈
一开始考虑用类似DP,因为若知道[3, 2, 6]栈为[2, 6], 8入栈,8与每一个栈内元素计算最小值,优化是用栈内的累计和,如2和6对应的累计和而不用每个元素计算。
参考了网上算法,栈内每个元素向左向右区间内(包括自己)均是最小值,所以出栈时候进行计算即可。
如[3, 2, 8, 7, 6, 9, 10, 4]栈是[2, 6, 9, 10]对应的下标,现在4入栈,9和10出栈后,6准备出栈。
prev_idx为6的下标4, i是7,6是[8, 7, 6], [7, 6], [6]三个区间的最小值prev_idx - stack[-1] = 3个区间,
而这些区间的最小值的和还要再乘以后面的大于它的数,如[7, 6]这个区间可以和这些区间合并[7, 6], [7, 6, 9], [7, 6, 9, 10], 所以(i - prev_idx) = 3
这就是arr[prev_idx] * (prev_idx - stack[-1]) * (i - prev_idx)的精髓
注意事项:
- 头尾加入最小值,加入头部因为公式需要栈内的前元素,这样可以处理只有一个元素出栈的情况。尾部加入最小值因为确保所有元素都出栈。
Python代码:
1 | def sumSubarrayMins(self, arr: List[int]) -> int: |
算法分析:
时间复杂度为O(n)
,空间复杂度O(n)