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类似的动态规划做了老半天，不是超空间就是超时。
实在没办法了只好看了单调栈的解法。