leetcode.907 子数组的最小值之和 - dp+单调栈

907. 子数组的最小值之和

好难啊，研究了一个下午了救命！！！

遍历a[i] 计算dp[i]   dp[i]——以a[i]为右边界的min值总和

以a[i]结尾时，分两种情况：

• 所有的子数组都以a[i]为最小值

             比如[3,0]  此时以a[i]=0为右边界的子数组为[0] [3,0] 

             则此时的 dp[i]=(i+1)*a[i]   也就是dp[1]=(1+1)*0=0

• 有一部分子数组以a[i]为最小值，另一部分子数组以前面一个比a[i]更小的数为最小值

​​​​​​​             比如[3,0,4,2,1]   此时[4,2,1]部分以a[i]为最小值 [1] [2,1] [4,2,1] 

             所以这一部分的值为3*a[i]=3，我们可以用单调栈找到离a[i]最近的比它小的值的下标

             (i - j)*a[i]

             

             而前一段[3,0]部分则在之前算过了，也就是dp[j]=dp[1]=0

             所以这一段结果就是：dp[i]=dp[j]+(i - j)*a[i]

最后累加每一次的dp[i]即可

class Solution {
    //动态规划 dp[i]:a[i] 为右边界的min总和  
    public int sumSubarrayMins(int[] arr) 
    {
        int len=arr.length;
        int res=0;
        int mod=1000000007;
        int[] dp= new int[len];
        dp[0]=arr[0];
        Deque st=new LinkedList<>();
        for(int i=0; i
        {
            while(!st.isEmpty()&&arr[st.peek()]>arr[i]) st.pop();//保证单调递增 找离它最近的比它小的值
            if(!st.isEmpty())
            {
                int j=st.peek(); 
                dp[i]=dp[j]+(i - j)*arr[i]; //j+1~i这一段以a[i]为最小值 0~j这一段以a[j]为最小值
            }else
                dp[i]=(i + 1)*arr[i]; //以a[i]为右边界的子数组都是a[i]为最小值
 
            res=(res+dp[i])%mod;//累加dp得到结果
            st.push(i);
        }
        return res;
    }
}