Daily LeetCode – day0091 0907. Sum of Subarray Minimums

import java.util.Stack;

// 0907. Sum of Subarray Minimums
class Solution {
public int sumSubarrayMins(int[] arr) {
final long MOD = 1000000007;
int n = arr.length;
int[] arr_0 = new int[n + 1];
System.arraycopy(arr, 0, arr_0, 0, n);
arr_0[n] = 0;
Stack<Integer> stack = new Stack<>();
long ans = 0L;
for (int i = 0; i <= n; ++i) {
while (!stack.isEmpty() && arr_0[stack.peek()] > arr_0[i]) {
int mid = stack.pop();
int left = stack.isEmpty() ? -1 : stack.peek();
ans = (ans + (long) (i - mid) * (mid - left) * arr_0[mid]) % MOD;
}
stack.push(i);
}
return (int) ans;
}
}
学习笔记:
这是一道单调栈的题目。
我使用了和0312类似的动态规划做了老半天,不是超空间就是超时。
实在没办法了只好看了单调栈的解法。


关于樊轶群

一个善良的理想主义者。
此条目发表在每日LeetCode分类目录。将固定链接加入收藏夹。

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注