单调栈leetcode.907

int MOD = (int)1e9+7;
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length, ans = 0;
        Deque<Integer> d = new ArrayDeque<>();//单调栈存储索引
        for (int r = 0; r <= n; r++) {
            int t = r < n ? arr[r] : 0;//遍历到n时，所有数都出栈
            //栈顶大于当前数，则栈顶的有效范围为[新栈顶+1,当前索引-1]，不包含左边相同值
            while (!d.isEmpty() && arr[d.peekLast()] > t) {
                int cur = d.pollLast();
                int l = d.isEmpty() ? 0 : d.peekLast() +1;//左边界
                int a = cur - l+1, b = r-1 - cur+1;//计算包含当前数的左右子数组数量
                ans += a * 1L * b % MOD * arr[cur] % MOD;
                ans %= MOD;
            }
            //栈顶不大于当前数，入栈，相同值以左边为最小
            d.addLast(r);
        }
        return ans;
    }