Sum of Subarray Minimums

[3] → 3
[3,1] → 1
[3,1,2] → 1
[1] → 1
[1,2] → 1
[2] → 2

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        int ans = 0;

        for(int i = 0; i < n; i++) {
            int mini = arr[i];
            for(int j = i; j < n; j++) {
                mini = min(mini, arr[j]);
                ans += mini;
            }
        }

        return ans;
    }
};

left = distance to previous smaller element
right = distance to next smaller element

previous smaller element (PSE)
next smaller element (NSE)

left = i - PSE[i]
right = NSE[i] - i

answer += arr[i] * left * right

PSE uses >
NSE uses >=

class Solution {
public:
    int sumSubarrayMins(vector<int>& arr) {
        int n = arr.size();
        vector<int> prev(n), next(n);
        stack<int> st;

        for(int i = 0; i < n; i++) {
            while(!st.empty() && arr[st.top()] > arr[i])
                st.pop();

            prev[i] = st.empty() ? -1 : st.top();
            st.push(i);
        }

        while(!st.empty()) st.pop();

        for(int i = n-1; i >= 0; i--) {
            while(!st.empty() && arr[st.top()] >= arr[i])
                st.pop();

            next[i] = st.empty() ? n : st.top();
            st.push(i);
        }

        long long ans = 0;

        for(int i = 0; i < n; i++) {
            long long left = i - prev[i];
            long long right = next[i] - i;
            ans += arr[i] * left * right;
        }

        return ans;
    }
};

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n = arr.length;
        int[] prev = new int[n];
        int[] next = new int[n];
        Stack<Integer> st = new Stack<>();

        for(int i = 0; i < n; i++) {
            while(!st.isEmpty() && arr[st.peek()] > arr[i])
                st.pop();

            prev[i] = st.isEmpty() ? -1 : st.peek();
            st.push(i);
        }

        st.clear();

        for(int i = n-1; i >= 0; i--) {
            while(!st.isEmpty() && arr[st.peek()] >= arr[i])
                st.pop();

            next[i] = st.isEmpty() ? n : st.peek();
            st.push(i);
        }

        long ans = 0;

        for(int i = 0; i < n; i++) {
            long left = i - prev[i];
            long right = next[i] - i;
            ans += arr[i] * left * right;
        }

        return (int) ans;
    }
}

class Solution:
    def sumSubarrayMins(self, arr):
        n = len(arr)
        stack = []
        prev = [-1]*n
        next = [n]*n

        for i in range(n):
            while stack and arr[stack[-1]] > arr[i]:
                stack.pop()

            prev[i] = stack[-1] if stack else -1
            stack.append(i)

        stack = []

        for i in range(n-1, -1, -1):
            while stack and arr[stack[-1]] >= arr[i]:
                stack.pop()

            next[i] = stack[-1] if stack else n
            stack.append(i)

        ans = 0

        for i in range(n):
            left = i - prev[i]
            right = next[i] - i
            ans += arr[i] * left * right

        return ans

function sumSubarrayMins(arr) {
    const n = arr.length;
    const prev = new Array(n);
    const next = new Array(n);
    const stack = [];

    for(let i = 0; i < n; i++) {
        while(stack.length && arr[stack[stack.length-1]] > arr[i]) {
            stack.pop();
        }

        prev[i] = stack.length ? stack[stack.length-1] : -1;
        stack.push(i);
    }

    stack.length = 0;

    for(let i = n-1; i >= 0; i--) {
        while(stack.length && arr[stack[stack.length-1]] >= arr[i]) {
            stack.pop();
        }

        next[i] = stack.length ? stack[stack.length-1] : n;
        stack.push(i);
    }

    let ans = 0;

    for(let i = 0; i < n; i++) {
        const left = i - prev[i];
        const right = next[i] - i;
        ans += arr[i] * left * right;
    }

    return ans;
}