907. Sum of Subarray Minimums

T: O(n)

S: O(n)

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        long mod = 1000000007;
        Deque<Integer> stack = new ArrayDeque<>();
        int[] nextSmaller = new int[n];
        int[] prevSmaller = new int[n];
        
        Arrays.fill(nextSmaller, n);
        Arrays.fill(prevSmaller, -1);
        
        // 1 4 7 2
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
                nextSmaller[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        stack.clear();
        
        for (int i = n - 1; i >= 0; i--) {
            // have equals! 去重的約定, for prev smaller or equal 都要算是邊界, 要 stop
            // ex: 5[ xxxx 5 xxxx 5xxx 5xxx 5], 左邊不能有重複的 5
            while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
                prevSmaller[stack.peek()] = i;
                stack.pop();
            }
            stack.push(i);
        }
        
        long result = 0L;
        for (int i = 0; i < n; i++) {
            // System.out.println("i:" + i + ",nextSmaller[i]:" + nextSmaller[i] + " prevSmaller[i]:" + prevSmaller[i]);
            result = (result + arr[i]*(nextSmaller[i] - i)%mod*(i - prevSmaller[i])%mod)%mod;
        }
        return (int)result;
    }
}

/*
1. naive:
for (i)
  for (j)
O(n^2)

2. mono stack
[3,1,2,4]

find left bound, right bound


if 3 is the smallest => range is 1 only [3], so 3*1 = 3

if 1 is the smallest, range is [3,1,2,4] =>
[3,1,2,4] = has 2*3 subarray = 6 
so 1*6 = 6

2=>
[2,4] = 2 => 2*2 = 4

4 => 4*1 = 4

3 + 6 + 4 + 4 = 17


1. find next smaller
2. find prev smaller
3.
cal number[i]*(nextSmaller index - i)*(i - prevSmaller index)





*/