[leetcode] problem 907 – sum of subarray minimums

// f(i) = (left[i] + 1) * (right[i] + 1)
// left[i]，能在A[i]左侧取得的最长宽度，使得在这个范围内A[i]是最小值,且都大于A[i]
// right[i], 能在A[i]右侧取得的最长宽度，使得在这个范围内A[i]是最小值，且都大于等于A[i]
public int (int[] A) {
    int result = 0;
    int mod = (int) 1e9 + 7;
    Stack<Integer> stack = new Stack<>();

    for (int i = 0; i <= A.length; i++) {
        int next = (i == A.length) ? -1 : A[i];

        while (!stack.isEmpty() && next < A[stack.peek()]) {
            int j = stack.pop();
            int k = stack.isEmpty() ? -1 : stack.peek();
            result = (result + A[j] * (j - k) * (i - j)) % mod;
        }

        stack.push(i);
    }

    return result;
}