企业官网建设流程全解析

网站建设和系统集成,做房产必知的发布房源网站,地产网站建设网,免费建站系统wordpress907. 子数组的最小值之和 问题描述 给定一个整数数组 arr#xff0c;计算所有非空连续子数组的最小值之和。由于答案可能很大#xff0c;返回结果对 10^9 7 取模。 示例#xff1a; 输入: arr [3,1,2,4] 输出: 17 解释: 子数组为 [3], [1], [2], [4], [3,1], [1,2], [2,4…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。算法思路单调栈对于每个元素arr[i]计算它作为最小值能贡献到多少个子数组中找到左边第一个小于arr[i]的位置left和右边第一个小于等于arr[i]的位置right以arr[i]为最小值的子数组数量为(i - left) * (right - i)总贡献为arr[i] * (i - left) * (right - i)为什么右边用小于等于而左边用小于避免重复计算当有相同元素时统一规定只有最左边的那个元素负责计算包含这些相同元素的子数组确保每个子数组的最小值只被计算一次代码实现方法一单调栈classSolution{privatestaticfinalintMOD1000000007;/** * 计算所有子数组最小值之和 * 使用单调栈计算每个元素的贡献度 * * param arr 输入数组 * return 所有子数组最小值之和对10^97取模 */publicintsumSubarrayMins(int[]arr){intnarr.length;// left[i] 表示 arr[i] 左边第一个小于 arr[i] 的元素位置不存在则为 -1int[]leftnewint[n];// right[i] 表示 arr[i] 右边第一个小于等于 arr[i] 的元素位置不存在则为 nint[]rightnewint[n];// 计算 left 数组 - 使用单调递增栈DequeIntegerstacknewArrayDeque();for(inti0;in;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(intin-1;i0;i--){// 维护单调递增栈弹出大于当前元素的索引while(!stack.isEmpty()arr[stack.peek()]arr[i]){stack.pop();}// 如果栈为空说明右边没有更小或相等的元素right[i]stack.isEmpty()?n:stack.peek();stack.push(i);}longresult0;// 计算每个元素的贡献度for(inti0;in;i){// 以 arr[i] 为最小值的子数组数量longcount(long)(i-left[i])*(right[i]-i);// 累加贡献度result(resultarr[i]*count)%MOD;}return(int)result;}}方法二一次遍历classSolution{privatestaticfinalintMOD1000000007;/** * 在单调栈弹出元素时直接计算贡献度 * * param arr 输入数组 * return 所有子数组最小值之和对10^97取模 */publicintsumSubarrayMins(int[]arr){intnarr.length;DequeIntegerstacknewArrayDeque();longresult0;// 添加哨兵元素简化边界处理for(inti0;in;i){// 当 i n 时当前值设为 -1确保弹出所有剩余元素intcurrent(in)?-1:arr[i];// 当栈不为空且当前元素小于栈顶元素时while(!stack.isEmpty()currentarr[stack.peek()]){// 弹出栈顶元素intmidstack.pop();// 左边界栈顶元素如果栈为空则为 -1intleftstack.isEmpty()?-1:stack.peek();// 右边界当前索引 iintrighti;// 计算以 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]方法一计算 left 数组i0: 栈空 →left[0] -1, 栈: [0]i1:arr[0]3 arr[1]1→ 弹出0栈空 →left[1] -1, 栈: [1]i2:arr[1]1 arr[2]2→left[2] 1, 栈: [1,2]i3:arr[2]2 arr[3]4→left[3] 2, 栈: [1,2,3]left [-1, -1, 1, 2]计算 right 数组i3: 栈空 →right[3] 4, 栈: [3]i2:arr[3]4 arr[2]2→ 弹出3栈空 →right[2] 4, 栈: [2]i1:arr[2]2 arr[1]1→ 弹出2栈空 →right[1] 4, 栈: [1]i0:arr[1]1 arr[0]3→right[0] 1, 栈: [1,0]right [1, 4, 4, 4]计算贡献度i0:count (0-(-1)) * (1-0) 1*1 1, 贡献 3*1 3i1:count (1-(-1)) * (4-1) 2*3 6, 贡献 1*6 6i2:count (2-1) * (4-2) 1*2 2, 贡献 2*2 4i3:count (3-2) * (4-3) 1*1 1, 贡献 4*1 4总和 3644 17测试用例publicstaticvoidmain(String[]args){SolutionsolutionnewSolution();// 测试用例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]// 1234123121 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] 222222 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右边界为n计算的子数组数量公式统一为(i-left) * (right-i)数据类型使用long防止中间计算溢出最后对10^9 7取模哨兵方法二中在数组末尾添加哨兵元素简化边界处理确保所有元素最终都会被弹出并计算贡献常见问题为什么右边用小于等于而左边用小于处理重复元素的情况确保每个子数组只被计算一次如果两边都用小于重复元素会被重复计算如果两边都用小于等于可能会漏掉某些情况(i-left) * (right-i)公式(i-left)表示以arr[i]为右端点的左边界选择数量(right-i)表示以arr[i]为左端点的右边界选择数量两者相乘就是所有包含arr[i]且arr[i]为最小值的子数组数量