算法随笔_27:最大宽度坡

上一篇:算法随笔_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.  元素i，j之间的宽度就是题目的最终答案。

   b.  在i，j之间，且比元素i小的那些元素中的某个元素做为最终答案的左端点。

   c.  在j右侧的所有元素中的某个元素做为最终答案的左端点。根据特征1，j右侧全部是比元素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]的左侧。又根据特征2，nums[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_max=0stack=[]nums_len=len(nums)for i in range(nums_len):if i==0: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:breakleft=stack[-1]while nums[j]>=nums[left]:w_max=max(w_max, j-left)stack.pop()if len(stack)==0:breakleft=stack[-1]return w_max