LeetCode 题解工作台
子数组的最小值之和
给定一个整数数组 arr ，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。 由于答案可能很大，因此 返回答案模 10^9 + 7 。 示例 1： 输入： arr = [3,1,2,4] 输出： 17 解释： 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,…
4
题型
6
代码语言
3
相关题
当前训练重点
中等 · 状态·转移·动态规划
答案摘要
题目要求的是每个子数组的最小值之和，实际上相当于，对于每个元素 ，求以 为最小值的子数组的个数，然后乘以 ，最后求和。 因此，题目的重点转换为：求以 为最小值的子数组的个数。对于 ，我们找出其左边第一个小于 的位置 ，右侧第一个小于等于 的位置 ，则以 为最小值的子数组的个数为 $(i - left[i]) \times (right[i] - i)$。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 状态·转移·动态规划 题型思路
题目描述
给定一个整数数组 arr，找到 min(b) 的总和，其中 b 的范围为 arr 的每个（连续）子数组。
由于答案可能很大，因此 返回答案模 10^9 + 7 。
示例 1：
输入：arr = [3,1,2,4] 输出：17 解释： 子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。 最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
示例 2：
输入：arr = [11,81,94,43,3] 输出：444
提示：
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104
解题思路
方法一：单调栈
题目要求的是每个子数组的最小值之和，实际上相当于，对于每个元素 ，求以 为最小值的子数组的个数，然后乘以 ，最后求和。
因此，题目的重点转换为：求以 为最小值的子数组的个数。对于 ，我们找出其左边第一个小于 的位置 ，右侧第一个小于等于 的位置 ，则以 为最小值的子数组的个数为 。
注意，这里为什么要求右侧第一个小于等于 的位置 ，而不是小于 的位置呢？这是因为，如果是右侧第一个小于 的位置 ，则会导致重复计算。
我们可以举个例子来说明，对于以下数组：
下标为 的元素大小为 ，左侧第一个小于 的元素下标为 ，如果我们求右侧第一个小于 的元素下标，可以得到下标为 。也即是说，子数组区间为 。注意，这里是开区间。
0 4 3 2 5 3 2 1
* ^ *
按照同样的方法，我们可以求出下标为 的元素的子数组区间，可以发现，其子数组区间也为 ，也即是说，下标为 和下标为 的元素的子数组区间是重复的。这样就造成了重复计算。
0 4 3 2 5 3 2 1
* ^ *
如果我们求的是右侧第一个小于等于其值的下标，就不会有重复问题，因为下标为 的子数组区间变为 ，下标为 的子数组区间为 ，两者不重复。
回到这道题上，我们只需要遍历数组，对于每个元素 ，利用单调栈求出其左侧第一个小于 的位置 ，右侧第一个小于等于 的位置 ，则以 为最小值的子数组的个数为 ，然后乘以 ，最后求和即可。
注意数据的溢出以及取模操作。
时间复杂度 ，空间复杂度 。其中 为数组 的长度。
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
left = [-1] * n
right = [n] * n
stk = []
for i, v in enumerate(arr):
while stk and arr[stk[-1]] >= v:
stk.pop()
if stk:
left[i] = stk[-1]
stk.append(i)
stk = []
for i in range(n - 1, -1, -1):
while stk and arr[stk[-1]] > arr[i]:
stk.pop()
if stk:
right[i] = stk[-1]
stk.append(i)
mod = 10**9 + 7
return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | Depends on the final approach |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Ensure the candidate is comfortable explaining dynamic programming with state transitions.
- question_mark
Check if the candidate can optimize the solution using a monotonic stack.
- question_mark
Look for understanding of the modulo operation in the context of large numbers.
常见陷阱
外企场景- error
Brute forcing the sum of minimums by iterating over all subarrays leads to a time complexity of O(n^2), which is inefficient for large arrays.
- error
Misunderstanding the use of the modulo operation can result in incorrect answers, especially for large sums.
- error
Overcomplicating the solution by using unnecessary data structures may hinder the performance of the algorithm.
进阶变体
外企场景- arrow_right_alt
Try solving this problem using a sliding window approach for further optimization.
- arrow_right_alt
Consider variations where the modulo is different, or the array contains negative numbers.
- arrow_right_alt
Attempt to solve this problem using a recursive approach with memoization.