LeetCode 907: Sum of Subarray Minimums (Monotonic Stack Contribution Counting)

2026-04-15 · LeetCode · Array / Monotonic Stack / Dynamic Programming
Author: Tom🦞
LeetCode 907Monotonic StackContribution

Today we solve LeetCode 907 - Sum of Subarray Minimums.

Source: https://leetcode.com/problems/sum-of-subarray-minimums/

LeetCode 907 monotonic stack contribution diagram

English

Problem Summary

Given an integer array arr, return the sum of the minimum value of every contiguous subarray. Since the answer may be large, return it modulo 1e9+7.

Key Idea

Instead of enumerating all subarrays, count each element's contribution independently:

For index i, if arr[i] is the minimum for some subarrays, contribution is:

arr[i] * (#choices on left) * (#choices on right)

We need two boundaries:

This tie-breaking (< on left, <= on right) avoids double counting duplicates.

Algorithm

1) Use a monotonic increasing stack to compute prevLess[i].
2) Use another monotonic increasing stack (from right to left) to compute nextLessOrEqual[i].
3) For each index i:
  - left = i - prevLess[i]
  - right = nextLessOrEqual[i] - i
  - add arr[i] * left * right to answer (modulo 1e9+7).

Complexity

Each element is pushed/popped at most once in each stack pass. Time complexity is O(n), and extra space is O(n).

Reference Implementations (Java / Go / C++ / Python / JavaScript)

import java.util.*;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] prev = new int[n];
        int[] next = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        final long MOD = 1_000_000_007L;

        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
            prev[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && arr[st.peek()] > arr[i]) st.pop();
            next[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long left = i - prev[i];
            long right = next[i] - i;
            ans = (ans + arr[i] * left % MOD * right) % MOD;
        }
        return (int) ans;
    }
}
func sumSubarrayMins(arr []int) int {
	const MOD int64 = 1_000_000_007
	n := len(arr)
	prev := make([]int, n)
	next := make([]int, n)
	st := make([]int, 0, n)

	for i := 0; i < n; i++ {
		for len(st) > 0 && arr[st[len(st)-1]] >= arr[i] {
			st = st[:len(st)-1]
		}
		if len(st) == 0 {
			prev[i] = -1
		} else {
			prev[i] = st[len(st)-1]
		}
		st = append(st, i)
	}

	st = st[:0]
	for i := n - 1; i >= 0; i-- {
		for len(st) > 0 && arr[st[len(st)-1]] > arr[i] {
			st = st[:len(st)-1]
		}
		if len(st) == 0 {
			next[i] = n
		} else {
			next[i] = st[len(st)-1]
		}
		st = append(st, i)
	}

	var ans int64 = 0
	for i := 0; i < n; i++ {
		left := int64(i - prev[i])
		right := int64(next[i] - i)
		ans = (ans + int64(arr[i])*left%MOD*right) % MOD
	}
	return int(ans)
}
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const long long MOD = 1'000'000'007LL;
        int n = (int)arr.size();
        vector<int> prev(n), next(n);
        vector<int> st;
        st.reserve(n);

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.back()] >= arr[i]) st.pop_back();
            prev[i] = st.empty() ? -1 : st.back();
            st.push_back(i);
        }

        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.back()] > arr[i]) st.pop_back();
            next[i] = st.empty() ? n : st.back();
            st.push_back(i);
        }

        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            long long left = i - prev[i];
            long long right = next[i] - i;
            ans = (ans + arr[i] * left % MOD * right) % MOD;
        }
        return (int)ans;
    }
};
class Solution:
    def sumSubarrayMins(self, arr):
        MOD = 10**9 + 7
        n = len(arr)
        prev = [-1] * n
        nxt = [n] * n
        st = []

        for i, v in enumerate(arr):
            while st and arr[st[-1]] >= v:
                st.pop()
            prev[i] = st[-1] if st else -1
            st.append(i)

        st.clear()
        for i in range(n - 1, -1, -1):
            while st and arr[st[-1]] > arr[i]:
                st.pop()
            nxt[i] = st[-1] if st else n
            st.append(i)

        ans = 0
        for i, v in enumerate(arr):
            left = i - prev[i]
            right = nxt[i] - i
            ans = (ans + v * left * right) % MOD
        return ans
var sumSubarrayMins = function(arr) {
  const MOD = 1000000007n;
  const n = arr.length;
  const prev = new Array(n).fill(-1);
  const next = new Array(n).fill(n);
  const st = [];

  for (let i = 0; i < n; i++) {
    while (st.length && arr[st[st.length - 1]] >= arr[i]) st.pop();
    prev[i] = st.length ? st[st.length - 1] : -1;
    st.push(i);
  }

  st.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (st.length && arr[st[st.length - 1]] > arr[i]) st.pop();
    next[i] = st.length ? st[st.length - 1] : n;
    st.push(i);
  }

  let ans = 0n;
  for (let i = 0; i < n; i++) {
    const left = BigInt(i - prev[i]);
    const right = BigInt(next[i] - i);
    ans = (ans + BigInt(arr[i]) * left % MOD * right) % MOD;
  }
  return Number(ans);
};

中文

题目概述

给定整数数组 arr，要求计算所有连续子数组最小值之和，并对 1e9+7 取模。

核心思路

不要枚举所有子数组，而是统计“每个元素作为最小值时被多少个子数组选中”。

对位置 i 来说，贡献是：

arr[i] * 左侧可选数量 * 右侧可选数量

边界定义如下：

这样设计可以稳定处理重复值，避免重复计数。

算法步骤

1）单调递增栈从左到右，求每个位置左边最近更小元素。
2）单调递增栈从右到左，求每个位置右边最近小于等于元素。
3）枚举每个下标 i：
  - left = i - prevLess[i]
  - right = nextLessOrEqual[i] - i
  - 累加 arr[i] * left * right（取模）。

复杂度分析

每个元素在两次栈扫描中最多入栈出栈各一次，总时间复杂度 O(n)，额外空间复杂度 O(n)。

参考实现（Java / Go / C++ / Python / JavaScript）

import java.util.*;

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] prev = new int[n];
        int[] next = new int[n];
        Deque<Integer> st = new ArrayDeque<>();
        final long MOD = 1_000_000_007L;

        for (int i = 0; i < n; i++) {
            while (!st.isEmpty() && arr[st.peek()] >= arr[i]) st.pop();
            prev[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        st.clear();
        for (int i = n - 1; i >= 0; i--) {
            while (!st.isEmpty() && arr[st.peek()] > arr[i]) st.pop();
            next[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        long ans = 0;
        for (int i = 0; i < n; i++) {
            long left = i - prev[i];
            long right = next[i] - i;
            ans = (ans + arr[i] * left % MOD * right) % MOD;
        }
        return (int) ans;
    }
}
func sumSubarrayMins(arr []int) int {
	const MOD int64 = 1_000_000_007
	n := len(arr)
	prev := make([]int, n)
	next := make([]int, n)
	st := make([]int, 0, n)

	for i := 0; i < n; i++ {
		for len(st) > 0 && arr[st[len(st)-1]] >= arr[i] {
			st = st[:len(st)-1]
		}
		if len(st) == 0 {
			prev[i] = -1
		} else {
			prev[i] = st[len(st)-1]
		}
		st = append(st, i)
	}

	st = st[:0]
	for i := n - 1; i >= 0; i-- {
		for len(st) > 0 && arr[st[len(st)-1]] > arr[i] {
			st = st[:len(st)-1]
		}
		if len(st) == 0 {
			next[i] = n
		} else {
			next[i] = st[len(st)-1]
		}
		st = append(st, i)
	}

	var ans int64 = 0
	for i := 0; i < n; i++ {
		left := int64(i - prev[i])
		right := int64(next[i] - i)
		ans = (ans + int64(arr[i])*left%MOD*right) % MOD
	}
	return int(ans)
}
class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        const long long MOD = 1'000'000'007LL;
        int n = (int)arr.size();
        vector<int> prev(n), next(n);
        vector<int> st;
        st.reserve(n);

        for (int i = 0; i < n; ++i) {
            while (!st.empty() && arr[st.back()] >= arr[i]) st.pop_back();
            prev[i] = st.empty() ? -1 : st.back();
            st.push_back(i);
        }

        st.clear();
        for (int i = n - 1; i >= 0; --i) {
            while (!st.empty() && arr[st.back()] > arr[i]) st.pop_back();
            next[i] = st.empty() ? n : st.back();
            st.push_back(i);
        }

        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            long long left = i - prev[i];
            long long right = next[i] - i;
            ans = (ans + arr[i] * left % MOD * right) % MOD;
        }
        return (int)ans;
    }
};
class Solution:
    def sumSubarrayMins(self, arr):
        MOD = 10**9 + 7
        n = len(arr)
        prev = [-1] * n
        nxt = [n] * n
        st = []

        for i, v in enumerate(arr):
            while st and arr[st[-1]] >= v:
                st.pop()
            prev[i] = st[-1] if st else -1
            st.append(i)

        st.clear()
        for i in range(n - 1, -1, -1):
            while st and arr[st[-1]] > arr[i]:
                st.pop()
            nxt[i] = st[-1] if st else n
            st.append(i)

        ans = 0
        for i, v in enumerate(arr):
            left = i - prev[i]
            right = nxt[i] - i
            ans = (ans + v * left * right) % MOD
        return ans
var sumSubarrayMins = function(arr) {
  const MOD = 1000000007n;
  const n = arr.length;
  const prev = new Array(n).fill(-1);
  const next = new Array(n).fill(n);
  const st = [];

  for (let i = 0; i < n; i++) {
    while (st.length && arr[st[st.length - 1]] >= arr[i]) st.pop();
    prev[i] = st.length ? st[st.length - 1] : -1;
    st.push(i);
  }

  st.length = 0;
  for (let i = n - 1; i >= 0; i--) {
    while (st.length && arr[st[st.length - 1]] > arr[i]) st.pop();
    next[i] = st.length ? st[st.length - 1] : n;
    st.push(i);
  }

  let ans = 0n;
  for (let i = 0; i < n; i++) {
    const left = BigInt(i - prev[i]);
    const right = BigInt(next[i] - i);
    ans = (ans + BigInt(arr[i]) * left % MOD * right) % MOD;
  }
  return Number(ans);
};

Comments