题目

907. 子数组的最小值之和【中等】

题解

单调栈

left[i]：以arr[i]元素为最右且最小的子序列数目
right[i]：以arr[i]元素为最左且最小的子序列数目

对于每一个arr[i]，

求左边第一个<arr[i]的元素：从左向右遍历数组，维护单调递增的栈。
如果栈顶元素>当前元素arr[i]，则将其弹出，直到栈顶元素<arr[i]，
栈顶元素即为左边第一个<arr[i]的元素arr[j]，此时left[i]=i-j
求右边第一个>=arr[i]的元素：从右向左遍历数组，维护单调递增的栈。
如果栈顶元素>当前元素arr[i]，则将其弹出，直到栈顶元素<=arr[i]，
栈顶元素即为右边第一个<=arr[i]的元素arr[k]，此时right[i]=k-i
连续子数组arr[j],arr[j+1],…,arr[k]的最小元素即为arr[i]，以arr[i]为最小元素的连续子序列数量为 $(i ? j) ? (k ? i)$

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n=arr.length;
        int[] left=new int[n];
        int[] right=new int[n];
        Deque<Integer>stack=new ArrayDeque<>();
        //计算left
        for(int i=0;i<n;i++){
            while(!stack.isEmpty()&&arr[i]<=arr[stack.peek()])
                stack.poll();
            if(!stack.isEmpty())
                left[i]=i-stack.peek();
            else
                left[i]=i+1;
            stack.push(i);
        }
        stack.clear();
        //计算right
        for(int i=n-1;i>=0;i--){
            while(!stack.isEmpty()&&arr[i]<arr[stack.peek()])
                stack.poll();
            if(!stack.isEmpty())
                right[i]=stack.peek()-i;
            else
                right[i]=n-i;
            stack.push(i);
        }
        //计算结果
        long res=0;
        final int MOD=1000000007;
        for(int i=0;i<n;i++){
            res=(res+(long)left[i]*right[i]*arr[i])%MOD;
        }
        return (int)res;
    }
}

时间复杂度： $O (n)$

空间复杂度： $O (n)$

单调栈+动态规划

状态定义：s[i][j] 表示子数组[ arr[j], arr[j+1],…,arr[i] ]的最小值
状态转移方程：
假设以arr[i]为最右且最小的最长子序列长度为k：
j>=i-k+1时，s[j][i]=arr[i]
j<i-k+1时，s[j][i] = s[j][i-k]
初始条件：
dp[i]=0
返回值：dp[i] 的和，0<=i<=n-1

算法

从左向右遍历数组并维护一个单调递增的栈，如果栈顶元素>=当前元素arr[i]，则弹出栈，此时栈顶元素即为左边第一个<当前值的元素
求出以当前值为最右且最小的子序列长度 k，根据递推公式求出 dp[i]，返回dp[i] 的和，0<=i<=n-1

class Solution {
    public int sumSubarrayMins(int[] arr) {
        int n=arr.length;
        int[] dp=new int[n];
        long res=0;
        final int MOD=1000000007;
        Deque<Integer>stack=new ArrayDeque<>();
        for(int i=0;i<n;i++){
            //维护单调栈
            while(!stack.isEmpty()&&arr[i]<=arr[stack.peek()])
                stack.poll();
            int k=stack.isEmpty()?i+1:i-stack.peek();//以arr[i]为最右且最小的最长子序列长度
            dp[i]=k*arr[i]+(stack.isEmpty()?0:dp[i-k]);
            res=(res+dp[i])%MOD;
            stack.push(i);
        }
        return (int)res;
    }
}