⚡Flashcard Drill➔
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

  1. Instead of enumerating subarrays, count how many subarrays have arr[j] as their minimum.
  2. Use a monotonic stack to find, for each j, the previous smaller element's index and the next smaller element's index.
  3. The count is (j - prev_smaller) * (next_smaller - j), and the contribution is arr[j] * count.
  4. 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 is j - left and of right choices is i - 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.
🎯 Drill This Card Now➔

🧩 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] 的下标。
  • 为什么用「严格小于」而非「小于等于」 :若两边都用非严格,重复元素会被重复计数。标准做法是「左边界用严格小于( &lt; ),右边界用小于等于( &lt;= )」,保证每个子数组的最小值被 唯一 的那个元素贡献。
  • 用单调栈求边界 :左边界用单调递增栈(弹出 ≥ 当前值的元素);右边界用另一个单调递增栈(弹出 &gt; 当前值的元素)。

常见陷阱

  • 两侧都用「严格小于」 :会导致重复元素被重复计数,结果偏大。必须一侧严格、一侧非严格。
  • 贡献公式写成 (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