网站浏览器兼容性,网站开发实习,纯字母logo设计,网站字体字号上一篇:算法随笔_26: 按奇偶排序数组-CSDN博客 题目描述如下:
给定一个整数数组 nums#xff0c;坡是元组 (i, j)#xff0c;其中 i j 且 nums[i] nums[j]。这样的坡的宽度为 j - i。
找出 nums 中的坡的最大宽度#xff0c;如果不存在#xff0c;返回 0 。
…上一篇:算法随笔_26: 按奇偶排序数组-CSDN博客 题目描述如下:
给定一个整数数组 nums坡是元组 (i, j)其中 i j 且 nums[i] nums[j]。这样的坡的宽度为 j - i。
找出 nums 中的坡的最大宽度如果不存在返回 0 。
示例 1
输入[6,0,8,2,1,5]
输出4
解释
最大宽度的坡为 (i, j) (1, 5): nums[1] 0 且 nums[5] 5.算法思路:
对于解决此题初步的想法是使用双层循环第一层循环枚举数组每个下标i第二层循环是从右往左寻找下标j 满足nums[i] nums[j]且最大的坡宽度 j - i。nums[i]只要找到了第一个j即可因为继续往左寻找也不会优于当前的j-i的宽度。
在第一层循环全部结束之后我们比较找到的所有下标的最大坡宽度其最大值就是整个数组的最大坡宽度。
接下来我们分析一下看看有没有可以优化的地方。
对于下标i假如以它为左端点的最大宽度坡的右端点在j处那么我们可以基于此分析出如下特征:
1. 大于等于元素i的数全部在j的左侧j右侧全部是比元素i小的数。
2. 对于在i和j之间的下标k如果下标k的元素大于等于下标i的元素那么比元素k大的所有数也必然在j的左侧那么满足条件的k的最右侧端点不可能大于j。因此k的最大坡宽度不可能大于j-i的宽度。
3. 最终的答案只能在下面的几种情形下产生: a. 元素ij之间的宽度就是题目的最终答案。 b. 在ij之间且比元素i小的那些元素中的某个元素做为最终答案的左端点。 c. 在j右侧的所有元素中的某个元素做为最终答案的左端点。根据特征1j右侧全部是比元素i小的数。
因此当我们尝试找最终答案的左端点的时候如果此时已经找到了元素i的最大宽度坡那么我们只需枚举比元素i小的那些元素作为左端点此时的效率就会大大提高。
如果上面提到的元素i就是nums[0]的话我们从左往右枚举数组找到第1个比nums[0]小的元素比如nums[5]后面又找到了nums[9]比nums[0]小但大于等于nums[5]那么我们考虑nums[9]为候选左端点吗结论是不需要。证明如下:
假设nums[5]的最大宽度坡的右端点在nums[p]处因为nums[9]在nums[5]的右侧且大于等于nums[5]根据特征1那就说明nums[9]肯定在nums[p]的左侧。又根据特征2nums[9]的最大宽度坡肯定不会大于nuns[5]最大宽度坡。因此nums[9]不需要作为候选左端点。
因此我们需要继续寻找比nums[5]更小的元素以此类推那所有的候选左端点就是从nums[0]开始单调递减的所有元素。因此我们可以用一个单调栈stack来存储所有左端点的下标。
此时左端点的搜索范围已经缩小我们再来看看如何寻找右端点。
对于右端点我们用指针j从右往左枚举数组。
1. 对于每一个访问的元素j我们让他与stack的栈顶stack[-1]元素做比较如果nums[j] nums[stack[-1]]我们把它们两个的距离做为一个候选的最大宽度坡dst_j。这个值就是栈顶元素做为左端点的最大宽度坡。此时因为我们已经找到栈顶元素的最大宽度坡所以栈顶元素已经不需要我们可以弹出栈顶元素。继续尝试用元素j与下一个栈顶元素比较。重复此步骤。
2. 如果nums[j] nums[stack[-1]]我们向左移动j一格重复步骤1。
算法整个的代码如下:
注: 我们把计算出的候选最大宽度坡与变量w_max不断比较取当前最大值存入w_max。最终的w_max就是答案。
class Solution(object):def maxWidthRamp(self, nums):w_max0stack[]nums_lenlen(nums)for i in range(nums_len):if i0:stack.append(i)elif nums[i]nums[stack[-1]]:stack.append(i)for j in range(nums_len-1,-1,-1):if len(stack)0:breakleftstack[-1]while nums[j]nums[left]:w_maxmax(w_max, j-left)stack.pop()if len(stack)0:breakleftstack[-1]return w_max
