算法题 子数组的最小值之和

907. 子数组的最小值之和

问题描述

给定一个整数数组arr，计算所有非空连续子数组的最小值之和。由于答案可能很大，返回结果对10^9 + 7取模。

示例：

输入: arr = [3,1,2,4] 输出: 17 解释: 子数组为 [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]。 最小值分别为 3, 1, 2, 4, 1, 1, 2, 1, 1, 1，和为 17。

算法思路

单调栈：

1. 对于每个元素arr[i]，计算它作为最小值能"贡献"到多少个子数组中
2. 找到左边第一个小于arr[i]的位置left和右边第一个小于等于arr[i]的位置right
3. 以arr[i]为最小值的子数组数量为(i - left) * (right - i)
4. 总贡献为arr[i] * (i - left) * (right - i)

为什么右边用"小于等于"而左边用"小于"？

• 避免重复计算：当有相同元素时，统一规定只有最左边的那个元素负责计算包含这些相同元素的子数组
• 确保每个子数组的最小值只被计算一次

代码实现

方法一：单调栈

classSolution{privatestaticfinalintMOD=1000000007;/** * 计算所有子数组最小值之和 * 使用单调栈计算每个元素的贡献度 * * @param arr 输入数组 * @return 所有子数组最小值之和（对10^9+7取模） */publicintsumSubarrayMins(int[]arr){intn=arr.length;// left[i] 表示 arr[i] 左边第一个小于 arr[i] 的元素位置，不存在则为 -1int[]left=newint[n];// right[i] 表示 arr[i] 右边第一个小于等于 arr[i] 的元素位置，不存在则为 nint[]right=newint[n];// 计算 left 数组 - 使用单调递增栈Deque<Integer>stack=newArrayDeque<>();for(inti=0;i<n;i++){// 维护单调递增栈，弹出大于等于当前元素的索引while(!stack.isEmpty()&&arr[stack.peek()]>=arr[i]){stack.pop();}// 如果栈为空，说明左边没有更小的元素left[i]=stack.isEmpty()?-1:stack.peek();stack.push(i);}// 清空栈，准备计算 right 数组stack.clear();// 计算 right 数组 - 使用单调递增栈for(inti=n-1;i>=0;i--){// 维护单调递增栈，弹出大于当前元素的索引while(!stack.isEmpty()&&arr[stack.peek()]>arr[i]){stack.pop();}// 如果栈为空，说明右边没有更小或相等的元素right[i]=stack.isEmpty()?n:stack.peek();stack.push(i);}longresult=0;// 计算每个元素的贡献度for(inti=0;i<n;i++){// 以 arr[i] 为最小值的子数组数量longcount=(long)(i-left[i])*(right[i]-i);// 累加贡献度result=(result+arr[i]*count)%MOD;}return(int)result;}}

方法二：一次遍历

classSolution{privatestaticfinalintMOD=1000000007;/** * 在单调栈弹出元素时直接计算贡献度 * * @param arr 输入数组 * @return 所有子数组最小值之和（对10^9+7取模） */publicintsumSubarrayMins(int[]arr){intn=arr.length;Deque<Integer>stack=newArrayDeque<>();longresult=0;// 添加哨兵元素简化边界处理for(inti=0;i<=n;i++){// 当 i == n 时，当前值设为 -1（确保弹出所有剩余元素）intcurrent=(i==n)?-1:arr[i];// 当栈不为空且当前元素小于栈顶元素时while(!stack.isEmpty()&&current<arr[stack.peek()]){// 弹出栈顶元素intmid=stack.pop();// 左边界：栈顶元素（如果栈为空则为 -1）intleft=stack.isEmpty()?-1:stack.peek();// 右边界：当前索引 iintright=i;// 计算以 arr[mid] 为最小值的子数组数量longcount=(long)(mid-left)*(right-mid);result=(result+(long)arr[mid]*count)%MOD;}stack.push(i);}return(int)result;}}

算法分析

• 时间复杂度：O(n)
  • 每个元素最多入栈和出栈一次，总体线性时间
• 空间复杂度：O(n)
  • 需要栈空间和辅助数组（方法一）或仅栈空间（方法二）

算法过程

输入：arr = [3,1,2,4]

方法一：

1. 计算 left 数组：

   • i=0: 栈空 →left[0] = -1, 栈: [0]
   • i=1:arr[0]=3 >= arr[1]=1→ 弹出0，栈空 →left[1] = -1, 栈: [1]
   • i=2:arr[1]=1 < arr[2]=2→left[2] = 1, 栈: [1,2]
   • i=3:arr[2]=2 < arr[3]=4→left[3] = 2, 栈: [1,2,3]
   • left = [-1, -1, 1, 2]

2. 计算 right 数组：

   • i=3: 栈空 →right[3] = 4, 栈: [3]
   • i=2:arr[3]=4 > arr[2]=2→ 弹出3，栈空 →right[2] = 4, 栈: [2]
   • i=1:arr[2]=2 > arr[1]=1→ 弹出2，栈空 →right[1] = 4, 栈: [1]
   • i=0:arr[1]=1 < arr[0]=3→right[0] = 1, 栈: [1,0]
   • right = [1, 4, 4, 4]

3. 计算贡献度：

   • i=0:count = (0-(-1)) * (1-0) = 1*1 = 1, 贡献 =3*1 = 3
   • i=1:count = (1-(-1)) * (4-1) = 2*3 = 6, 贡献 =1*6 = 6
   • i=2:count = (2-1) * (4-2) = 1*2 = 2, 贡献 =2*2 = 4
   • i=3:count = (3-2) * (4-3) = 1*1 = 1, 贡献 =4*1 = 4
   • 总和 =3+6+4+4 = 17

测试用例

publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：标准示例int[]arr1={3,1,2,4};System.out.println("Test 1: "+solution.sumSubarrayMins(arr1));// 17// 测试用例2：递增数组int[]arr2={1,2,3,4};System.out.println("Test 2: "+solution.sumSubarrayMins(arr2));// 20// [1]+[2]+[3]+[4]+[1,2]+[2,3]+[3,4]+[1,2,3]+[2,3,4]+[1,2,3,4]// = 1+2+3+4+1+2+3+1+2+1 = 20// 测试用例3：递减数组int[]arr3={4,3,2,1};System.out.println("Test 3: "+solution.sumSubarrayMins(arr3));// 20// 每个子数组的最小值都是最后一个元素// 测试用例4：相同元素int[]arr4={2,2,2};System.out.println("Test 4: "+solution.sumSubarrayMins(arr4));// 12// [2]+[2]+[2]+[2,2]+[2,2]+[2,2,2] = 2+2+2+2+2+2 = 12// 测试用例5：单元素int[]arr5={5};System.out.println("Test 5: "+solution.sumSubarrayMins(arr5));// 5// 测试用例6：大数值（测试取模）int[]arr6={100000};System.out.println("Test 6: "+solution.sumSubarrayMins(arr6));// 100000// 测试用例7：复杂情况int[]arr7={71,55,82,55};System.out.println("Test 7: "+solution.sumSubarrayMins(arr7));// 539// 测试用例8：包含0int[]arr8={3,0,2,1};System.out.println("Test 8: "+solution.sumSubarrayMins(arr8));// 7}

关键点

1. 贡献度：

   • 不直接枚举所有子数组，而是计算每个元素作为最小值的贡献

2. 单调栈：

   • 用于高效找到每个元素左右边界
   • 左边找"小于"，右边找"小于等于"避免重复计算

3. 边界处理：

   • 不存在更小元素时，左边界为-1，右边界为n
   • 计算的子数组数量公式统一为(i-left) * (right-i)

4. 数据类型：

   • 使用long防止中间计算溢出
   • 最后对10^9 + 7取模

5. 哨兵：

   • 方法二中在数组末尾添加哨兵元素，简化边界处理
   • 确保所有元素最终都会被弹出并计算贡献

常见问题

1. 为什么右边用"小于等于"而左边用"小于"？

   • 处理重复元素的情况，确保每个子数组只被计算一次
   • 如果两边都用"小于"，重复元素会被重复计算
   • 如果两边都用"小于等于"，可能会漏掉某些情况

2. (i-left) * (right-i)公式？

   • (i-left)表示以arr[i]为右端点的左边界选择数量
   • (right-i)表示以arr[i]为左端点的右边界选择数量
   • 两者相乘就是所有包含arr[i]且arr[i]为最小值的子数组数量