【LeetCode】Day169-子数组的最小值之和

题目

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

题解

单调栈

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

对于每一个arr[i]，

• 求左边第一个从左向右遍历数组，维护单调递增的栈。
  如果栈顶元素>当前元素arr[i]，则将其弹出，直到栈顶元素 栈顶元素即为左边第一个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)\ast (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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

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

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

单调栈+动态规划

1. 状态定义：s[i][j] 表示子数组[ arr[j], arr[j+1],…,arr[i] ]的最小值

2. 状态转移方程：
   假设以arr[i]为最右且最小的最长子序列长度为k：
   j>=i-k+1时，s[j][i]=arr[i]
   j

3. 初始条件：
   dp[i]=0

4. 返回值：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;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

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

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