NeetCode #374LC-907MediumStack
← Back to All Problems#374 · #907 · Sum of Subarray Minimums(子数组的最小值之和)
📌 Problem Statement & Constraints
Given an array of integers
arr, return the sum of min(b) over every contiguous subarray b, modulo 10^9 + 7. Constraints: 1 <= arr.length <= 3 * 10^4, 1 <= arr[i] <= 3 * 10^4.💡 Core Algorithmic Approaches
- Instead of enumerating subarrays, count how many subarrays have
arr[j]as their minimum. - Use a monotonic stack to find, for each
j, the previous smaller element's index and the next smaller element's index. - The count is
(j - prev_smaller) * (next_smaller - j), and the contribution isarr[j] * count. - Use
>=on one side and>on the other (here>=when popping) so that subarrays with equal minima are counted exactly once.
💻 Benchmark Python3 Implementation
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
MOD = 10 ** 9 + 7
n = len(arr)
st = []
total = 0
for i in range(n + 1):
# the sentinel i == n flushes the stack
while st and (i == n or arr[st[-1]] >= arr[i]):
j = st.pop()
left = st[-1] if st else -1 # previous strictly smaller
# arr[j] is the minimum for (j - left) * (i - j) subarrays
total += arr[j] * (j - left) * (i - j)
st.append(i)
return total % MOD⚡ Complexity Deep Dive
⏱️ Time Complexity
O(n): each index is pushed once and popped at most once.
💾 Space Complexity
O(n) for the stack.
⚠️ Interview Pitfalls & Follow-ups
- Using
>in the pop condition: with duplicates, some subarrays would be counted twice and others not at all. One side must be non-strict, the other strict. - Computing the width as
i - left - 1: the count of left choices isj - leftand of right choices isi - j; multiplying those is correct, whereas the naive width formula is not. - Omitting the sentinel: elements left on the stack would never contribute.
- Enumerating all subarrays: O(n^2) with n = 3 * 10^4 is 4.5 * 10^8 operations.
⚡
Test muscle memory on this topic via 3-Layer Flashcards
Active Recall: Mentally formulate Prompt ➔ Math Derivation ➔ Benchmark Implementation in 3 minutes.
🧩 Related Stack Problems
中文速览与面试要点
子数组的最小值之和
给定一个整数数组 arr,找到 min(b) 的总和,其中 b 的范围为 arr 的每个(连续)子数组。由于答案可能很大,因此 返回答案对 10^9 + 7 取余 后的结果。约束:1 ≤ arr.length ≤ 3 × 10^4;1 ≤ arr[i] ≤ 3 × 10^4。
核心要点
- 贡献法 + 单调栈(标准解) :换个角度——求「每个元素作为最小值时,能贡献多少个包含它的子数组」。
- 以 arr[i] 为最小值的子数组数 = (i − left) × (right − i) ,其中 left 是左侧第一个 严格小于 arr[i] 的下标,right 是右侧第一个 严格小于 arr[i] 的下标。
- 为什么用「严格小于」而非「小于等于」 :若两边都用非严格,重复元素会被重复计数。标准做法是「左边界用严格小于( < ),右边界用小于等于( <= )」,保证每个子数组的最小值被 唯一 的那个元素贡献。
- 用单调栈求边界 :左边界用单调递增栈(弹出 ≥ 当前值的元素);右边界用另一个单调递增栈(弹出 > 当前值的元素)。
常见陷阱
- 两侧都用「严格小于」 :会导致重复元素被重复计数,结果偏大。必须一侧严格、一侧非严格。
- 贡献公式写成 (i − left) * (right − i) 之外的形式 :正确是「左端点的可选数 × 右端点的可选数」。
- 用「枚举所有子数组」 :O(n²) 在 n = 3 × 10^4 时约 4.5 × 10^8,会超时。
- 忘记取模 :结果会非常大。
- left[i] 初值设为 0 而非 −1 :当没有左侧更小元素时,左端点可选范围是 0..i (共 i+1 个),对应 i − (−1) = i + 1 。
参考实现
class Solution:
def sumSubarrayMins(self, arr: list[int]) -> int:
MOD = 10 ** 9 + 7
n = len(arr)
# 左边界:左侧第一个「严格小于」arr[i] 的下标
left = [-1] * n
stack = []
for i in range(n):
while stack and arr[stack[-1]] >= arr[i]: # 弹出 >= 的
stack.pop()
left[i] = stack[-1] if stack else -1
stack.append(i)
# 右边界:右侧第一个「小于等于」arr[i] 的下标
right = [n] * n
stack = []
for i in range(n - 1, -1, -1):
while stack and arr[stack[-1]] > arr[i]: # 弹出 > 的
stack.pop()
right[i] = stack[-1] if stack else n
stack.append(i)
# 贡献求和
total = 0
for i in range(n):
total = (total + arr[i] * (i - left[i]) * (right[i] - i)) % MOD
return total