手机页面网站模板怎么卖,重庆做网络推广的公司,中信建设有限责任公司资阳分公司,网站代前言 Weekly Contest 116 的最大宽度坡#xff1a; 给定一个整数数组 A#xff0c;坡是元组 (i, j)#xff0c;其中 i j 且 A[i] A[j]。这样的坡的宽度为 j - i。 找出 A 中的坡的最大宽度#xff0c;如果不存在#xff0c;返回 0 。 示例1#xff1a; 输入 给定一个整数数组 A坡是元组 (i, j)其中 i j 且 A[i] A[j]。这样的坡的宽度为 j - i。 找出 A 中的坡的最大宽度如果不存在返回 0 。 示例1 输入[6,0,8,2,1,5]
输出4
解释
最大宽度的坡为 (i, j) (1, 5): A[1] 0 且 A[5] 5. 示例2 输入[9,8,1,0,1,9,4,0,4,1]
输出7
解释
最大宽度的坡为 (i, j) (2, 9): A[2] 1 且 A[9] 1. 提示 2 A.length 500000 A[i] 50000 解题思路 本题中的元组个人感觉是一个烟雾弹就算不了解元组的概念也能够完成本题。本题的逻辑虽然不复杂但是如果只是按照逻辑实现会出现Time Limit Exceeded的情况需要在实现的代码上进行算法的优化减少循环次数从而避免 Time Limit Exceeded。 本题的逻辑实现其实很简单使用双指针法即可完成。首先第一个指针有序的遍历每个元素当第一个指针指向一个元素时第二个指针则遍历这个元素后的每一个元素并依次与第一个指针指向的元素进行比较如果值比它小则计算坡度并与当前最大坡度进行比较记录较大值。 实现代码 逻辑实现 这个代码是根据题意实现的基础代码会出现Time Limit Exceeded的情况 public int maxWidthRamp(int[] A) {//最大宽度int maxWidth0;for(int i0;iA.length-1;i){for(int ji1;jA.length;j){if(A[i]A[j]){//比较两个指针指向的元素值满足A[i] A[j]则计算宽度maxWidthmaxWidth(j-i)?maxWidth:j-i;//计算最大宽度}}}return maxWidth;} 算法优化 /*** 962. 最大宽度坡* param A* return*/public int maxWidthRamp(int[] A) {//最大宽度int maxWidth0;//理论最大宽度int mayMaxWidth0;for(int i0;iA.length-1;i){//每次循环时理论最大宽度应该不会超过数组最后一个元素的索引减去当前元素索引mayMaxWidthA.length-1-i;if(maxWidthmayMaxWidth){//超过理论最大值表示已经找到最大宽度坡直接终止循环break;}for(int ji1;jA.length;j){if(A[i]A[j]){//比较两个指针指向的元素值满足A[i] A[j]则计算宽度maxWidthmaxWidth(j-i)?maxWidth:j-i;//计算最大宽度}}}return maxWidth;}
