算法题 最大宽度坡

最大宽度坡

问题描述

给定一个整数数组nums，定义一个坡为元组(i, j)，其中i < j且nums[i] <= nums[j]。坡的宽度为j - i。

请返回数组中最大宽度坡的宽度。如果没有坡，返回 0。

示例：

输入: [6,0,8,2,1,5] 输出: 4 解释: 最大宽度坡为 (1, 5): nums[1] = 0 <= nums[5] = 5，宽度 = 5 - 1 = 4 输入: [9,8,1,0,1,9,4,0,4,1] 输出: 7 解释: 最大宽度坡为 (2, 9): nums[2] = 1 <= nums[9] = 1，宽度 = 9 - 2 = 7

算法思路

方法一：暴力

对每个可能的左端点i，遍历所有右端点j > i，检查是否满足nums[i] <= nums[j]，并记录最大宽度。

时间复杂度：O(n²)，对于 n=50000 会超时。

方法二：单调栈 + 二分搜索

1. 构建候选左端点：使用单调递减栈存储可能作为左端点的索引

   • 只有当nums[i]小于栈顶元素对应的值时，才将i入栈
   • 保证了栈中索引对应的值是严格递减的

2. 从右向左寻找右端点：从数组末尾开始遍历，对每个位置j：

   • 在单调栈中找到最左边的索引i，使得nums[i] <= nums[j]
   • 由于栈中值是递减的，可以使用二分搜索快速定位

代码实现

方法一：暴力

classSolution{/** * 暴力：检查所有可能的坡 * * @param nums 输入数组 * @return 最大宽度坡的宽度 */publicintmaxWidthRamp(int[]nums){intmaxRamp=0;intn=nums.length;for(inti=0;i<n;i++){for(intj=i+1;j<n;j++){if(nums[i]<=nums[j]){maxRamp=Math.max(maxRamp,j-i);}}}returnmaxRamp;}}

方法二：单调栈 + 二分搜索

importjava.util.*;classSolution{/** * 使用单调栈和二分搜索求解最大宽度坡 * * @param nums 输入数组 * @return 最大宽度坡的宽度 */publicintmaxWidthRamp(int[]nums){intn=nums.length;Stack<Integer>stack=newStack<>();// 构建单调递减栈，存储候选左端点的索引// 栈中索引对应的值是严格递减的for(inti=0;i<n;i++){// 只有当当前元素小于栈顶元素对应的值时才入栈if(stack.isEmpty()||nums[i]<nums[stack.peek()]){stack.push(i);}}intmaxRamp=0;// 从右向左遍历，寻找最佳右端点for(intj=n-1;j>=0;j--){// 在单调栈中找到最左边的索引i，使得nums[i] <= nums[j]// 由于栈中值递减，可以弹出所有满足条件的栈顶元素while(!stack.isEmpty()&&nums[stack.peek()]<=nums[j]){inti=stack.pop();maxRamp=Math.max(maxRamp,j-i);}}returnmaxRamp;}}

算法分析

方法一：暴力

• 时间复杂度：O(n²)
• 空间复杂度：O(1)

方法二：单调栈 + 二分搜索

• 时间复杂度：O(n)
  • 构建单调栈：O(n)
  • 从右向左遍历：O(n)
  • 每个元素最多入栈和出栈一次
• 空间复杂度：O(n)
  • 单调栈最多存储 n 个元素

算法过程

输入[9,8,1,0,1,9,4,0,4,1]：

1：构建单调递减栈

• i=0: stack=[0] (值9)
• i=1: 8<9, stack=[0,1] (值9,8)
• i=2: 1<8, stack=[0,1,2] (值9,8,1)
• i=3: 0<1, stack=[0,1,2,3] (值9,8,1,0)
• i=4: 1>0, 跳过
• i=5: 9>0, 跳过
• i=6: 4>0, 跳过
• i=7: 0==0, 跳过
• i=8: 4>0, 跳过
• i=9: 1>0, 跳过

最终栈：[0,1,2,3] 对应值 [9,8,1,0]

2：从右向左遍历找最大坡

• j=9, nums[9]=1:
  • 比较栈顶 nums[3]=0 ≤ 1 , 宽度=9-3=6, maxRamp=6
  • 比较栈顶 nums[2]=1 ≤ 1 , 宽度=9-2=7, maxRamp=7
  • 比较栈顶 nums[1]=8 > 1 , 停止
• j=8, nums[8]=4:
  • 比较栈顶 nums[1]=8 > 4 , 跳过
• j=7, nums[7]=0:
  • 比较栈顶 nums[1]=8 > 0 , 跳过
• j=6, nums[6]=4:
  • 比较栈顶 nums[1]=8 > 4 , 跳过
• j=5, nums[5]=9:
  • 比较栈顶 nums[1]=8 ≤ 9 , 宽度=5-1=4, maxRamp=7
  • 比较栈顶 nums[0]=9 ≤ 9 , 宽度=5-0=5, maxRamp=7
  • 栈空，停止

最终结果：7

测试用例

publicclassTestMaxWidthRamp{publicstaticvoidmain(String[]args){Solutionsolution=newSolution();// 测试用例1：基本示例int[]nums1={6,0,8,2,1,5};System.out.println("Test 1: "+solution.maxWidthRamp(nums1));// 4// 测试用例2：复杂示例int[]nums2={9,8,1,0,1,9,4,0,4,1};System.out.println("Test 2: "+solution.maxWidthRamp(nums2));// 7// 测试用例3：严格递减数组（无坡）int[]nums3={9,8,7,6,5,4,3,2,1,0};System.out.println("Test 3: "+solution.maxWidthRamp(nums3));// 0// 测试用例4：严格递增数组int[]nums4={0,1,2,3,4,5,6,7,8,9};System.out.println("Test 4: "+solution.maxWidthRamp(nums4));// 9// 测试用例5：所有元素相同int[]nums5={5,5,5,5,5};System.out.println("Test 5: "+solution.maxWidthRamp(nums5));// 4// 测试用例6：单元素int[]nums6={1};System.out.println("Test 6: "+solution.maxWidthRamp(nums6));// 0// 测试用例7：两元素递增int[]nums7={1,2};System.out.println("Test 7: "+solution.maxWidthRamp(nums7));// 1// 测试用例8：两元素递减int[]nums8={2,1};System.out.println("Test 8: "+solution.maxWidthRamp(nums8));// 0}}

关键点

1. 单调栈：

   • 过滤掉"无用"的左端点
   • 保证栈中候选左端点的值严格递减
   • 使得后续查找更高效

2. 为什么从右向左遍历：

   • 对于固定的左端点，希望右端点尽可能靠右
   • 从右向左遍历可以确保找到每个左端点对应的最佳右端点

3. 边界情况处理：

   • 严格递减数组：返回0
   • 严格递增数组：返回n-1
   • 所有元素相同：返回n-1

常见问题

1. 为什么单调栈要维护递减序列？

   • 如果存在i1 < i2且nums[i1] <= nums[i2]，那么i2永远不会成为最优左端点
   • i1位置更靠左，值更小或相等，对于任何右端点j，如果(i2,j)是坡，那么(i1,j)也是坡且宽度更大

2. 能否从左向右遍历找右端点？

   • 效率较低
   • 从右向左遍历可以利用贪心思想：一旦找到满足条件的左端点，就可以立即计算宽度