class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
}
};
907. 子数组的最小值之和
给定一个整数数组 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
原站题解
cpp 解法, 执行用时: 68 ms, 内存消耗: 39 MB, 提交时间: 2023-11-27 06:55:04
class Solution {
const int MOD = 1e9 + 7;
public:
int sumSubarrayMins(vector<int> &arr) {
long ans = 0L;
arr.push_back(-1);
stack<int> st;
st.push(-1); // 哨兵
for (int r = 0; r < arr.size(); ++r) {
while (st.size() > 1 && arr[st.top()] >= arr[r]) {
int i = st.top();
st.pop();
ans += (long) arr[i] * (i - st.top()) * (r - i); // 累加贡献
}
st.push(r);
}
return ans % MOD;
}
};
java 解法, 执行用时: 16 ms, 内存消耗: 47.2 MB, 提交时间: 2023-08-14 09:55:01
class Solution {
private static final long MOD = (long) 1e9 + 7;
public int sumSubarrayMins(int[] arr) {
var ans = 0L;
var st = new ArrayDeque<Integer>();
st.push(-1); // 哨兵
for (var r = 0; r <= arr.length; ++r) {
var x = r < arr.length ? arr[r] : -1; // 假设 arr 末尾有个 -1
while (st.size() > 1 && arr[st.peek()] >= x) {
var i = st.pop();
ans += (long) arr[i] * (i - st.peek()) * (r - i); // 累加贡献
}
st.push(r);
}
return (int) (ans % MOD);
}
}
golang 解法, 执行用时: 48 ms, 内存消耗: 7.1 MB, 提交时间: 2023-08-14 09:54:35
func sumSubarrayMins(arr []int) (ans int) {
arr = append(arr, -1)
st := []int{-1} // 哨兵
for r, x := range arr {
for len(st) > 1 && arr[st[len(st)-1]] >= x {
i := st[len(st)-1]
st = st[:len(st)-1]
ans += arr[i] * (i - st[len(st)-1]) * (r - i) // 累加贡献
}
st = append(st, r)
}
return ans % (1e9 + 7)
}
python3 解法, 执行用时: 188 ms, 内存消耗: 18.5 MB, 提交时间: 2022-10-28 09:18:19
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
# 左边界 left[i] 为左侧严格小于 arr[i] 的最近元素位置（不存在时为 -1）
left, st = [-1] * n, []
for i, x in enumerate(arr):
while st and arr[st[-1]] >= x:
st.pop() # 移除无用数据
if st: left[i] = st[-1]
st.append(i)
# 右边界 right[i] 为右侧小于等于 arr[i] 的最近元素位置（不存在时为 n）
right, st = [n] * n, []
for i in range(n - 1, -1, -1):
while st and arr[st[-1]] > arr[i]:
st.pop() # 移除无用数据
if st: right[i] = st[-1]
st.append(i)
ans = 0
for i, (x, l, r) in enumerate(zip(arr, left, right)):
ans += x * (i - l) * (r - i) # 累加贡献
return ans % (10 ** 9 + 7)
python3 解法, 执行用时: 152 ms, 内存消耗: 18.3 MB, 提交时间: 2022-10-28 09:17:52
class Solution:
def sumSubarrayMins(self, arr: List[int]) -> int:
n = len(arr)
left, right, st = [-1] * n, [n] * n, []
for i, x in enumerate(arr):
while st and arr[st[-1]] >= x:
right[st.pop()] = i # i 恰好是栈顶的右边界
if st: left[i] = st[-1]
st.append(i)
ans = 0
for i, (x, l, r) in enumerate(zip(arr, left, right)):
ans += x * (i - l) * (r - i) # 累加贡献
return ans % (10 ** 9 + 7)
python3 解法, 执行用时: 160 ms, 内存消耗: 18.4 MB, 提交时间: 2022-10-28 09:14:35
class Solution(object):
def sumSubarrayMins(self, A):
MOD = 10**9 + 7
stack = []
ans = dot = 0
for j, y in enumerate(A):
# Add all answers for subarrays [i, j], i <= j
count = 1
while stack and stack[-1][0] >= y:
x, c = stack.pop()
count += c
dot -= x * c
stack.append((y, count))
dot += y * count
ans += dot
return ans % MOD