算法随笔_29:最大宽度坡_方法3
上一篇:算法随笔_28:最大宽度坡_方法2-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.
=====
上一篇讲了最大宽度坡的解法2，那个算法的时间复杂度为O(nlogn) 。
这篇文章我们从另一个角度来考虑这个问题，给出解法3。我们利用二分查找法来解决这个问题。
我们从右往左枚举数组，对于访问的每一个元素i我们考虑其为最大宽度坡的左端点，并寻找它的最大宽度坡。枚举完数组所有元素之后，取所有最大宽度坡的最大值即为答案。
由于枚举一遍左端点需要O(n) 的时间复杂度。我们寻找每个元素i的最大的右端点的时间复杂度需要低于O(n) 。否则的话，就变成了双层循环，暴力解法了。下面我们就给出解法3的步骤和思路。
当我们不断从右向左枚举元素i的时候，我们维护一个不断升序的数组sort_nums。这个数组就是最终题解的右端点的候选集。也就是说，最终的题解只能在这个候选集中选出右端点。
我们每访问一个元素i，就和sort_nums中的最大值比较，大于最大值的元素，放入sort_nums末尾，小于等于最大值的元素，不放入sort_nums。因此这个数组的特征就是元素值是升序的，但元素对应的索引值是下降的。
刚才提到，在维护sort_nums数组时，如果元素i小于等于sort_nums最大值，并不放入sort_nums数组，那这会影响最终结果吗？结论是不会影响最终答案。下面给出证明:
假如元素i是最终答案的右端点，我们设它的左端点为left，由于元素i的值小于等于sort_nums最大值，且元素i的索引也小于sort_nums最大值的索引p。索引p也可以成为元素left的右端点，且(left, p) 的距离肯定比(left, i) 的距离更大。此时与假设矛盾。因此以元素i为右端点的最大宽度坡不可能是最终的答案。所以无需放入sort_nums数组。
对于元素i，它最大宽度坡的右端点需要大于等于它，且尽可能的离它远，即，尽可能的索引值要大。因此我们需要从左向右枚举sort_nums数组，找到第一个大于等于元素i的元素j即可停止枚举。元素j就是元素i的最大宽度坡的右端点。因为sort_nums数组中的元素对应的索引值就是从大到小排列的。
此处，我们还可以做进一步的优化。观察到这个数组的元素是从小到大排列的，既然是有序的，我们就可以用二分查找法来找到第一个大于等于元素i的元素j。
下面是代码实现:
class Solution(object):
def biSearch(self,num, sort_nums):
lf=0
rg=len(sort_nums)
while lf<rg:
mid=lf+(rg-lf)//2
if num > sort_nums[mid][0]:
lf=mid+1
else:
rg=mid
return lf
def maxWidthRamp(self, nums):
nums_len=len(nums)
w_max=0
sort_nums=[[nums[-1],nums_len-1]]
for i in range(nums_len-2,-1,-1):
lf=self.biSearch(nums[i],sort_nums)
if lf < len(sort_nums):
rg=sort_nums[lf][1]
w_max=max(w_max,rg-i)
else:
sort_nums.append([nums[i], i])
return w_max
***********
代码注解:
1. 为了让大家更清楚了解此题的二分查找过程，在代码里没有使用python的bisect模块。而是实现了一个biSearch。
2. 代码里看起来也没有明显的实现这个过程 (我们每访问一个元素i，就和sort_nums中的最大值比较，大于最大值的元素，放入sort_nums末尾) 。其实这个步骤，在二分查找的时候就已经实现了。因为如果查找后的左侧索引lf达到了数组的长度，说明元素i比sort_nums中的任何值都大。它可以放入sort_nums的末尾。
3. sort_nums数组里的每个元素也是一个数组，它保存了两个值。一个是原数组的元素值，一个是原数组的元素索引。
***********
此算法的时间复杂度为O(nlogn) 。因为左端点的一次遍历为O(n) ，右端点二分查找为O(logn) 。