上一篇:算法随笔_27:最大宽度坡-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.
=====
上一篇讲了最大宽度坡的一个算法，单调栈，那个算法的时间复杂度为O(n) 。
这篇文章咱们来讲一下这道题的另一种解法。虽然这个时间复杂度稍微慢一些，但是对于拓宽我们的解题思路是有帮助的。
我们考虑先把原数组按升序排序，得到新数组sort_nums，那么sort_nums对应原数组的索引就是数组sort_inds。由于在sort_inds中每个元素都有可能是最终题解的右端点，所以我们通过枚举sort_inds右端点来找到答案。
假如当右端点j固定时，如何寻找它的最大宽度坡的左端点i呢？
我们注意到，由于sort_nums元素是从小到大排序的，所以要从sort_inds中找到右端点j的左端点i，只能从右端点j的左侧寻找。此时我们缩小了查询左端点的搜索范围。
我们继续看，如果对于每个右端点j，我们都要从sort_inds的开始处寻找，好像也会出现重复计算的情况。其实，我们只需要找到右端点j左侧的最小索引ind_min，然后用j减去ind_min。如果值是负数，忽略它。如果值是正数，我们就找到了右端点j的最大宽度坡的左端点为ind_min。为什么这么说呢？对于右端点j，在它所有可能的左端点中，必然要找一个离它最远的那个，所以当然要找索引值最小的那个。
对于ind_min，我们每枚举一个元素都与ind_min比较，把较小值存入ind_min。我们设最终的最大宽度坡为w_max，我们每找到一个最大宽度坡，都与w_max比较，把较大值存入w_max。
此算法的时间复杂度为O(nlogn) 。
下面是python代码实现:
class Solution(object):def maxWidthRamp(self, nums):sort_inds=[i[0] for i in sorted(enumerate(nums), key=lambda x:x[1])]ind_min=float('inf')w_max=0for ind in sort_inds:w_max=max(w_max,ind-ind_min)ind_min=min(ind_min,ind)return w_max注: 对于下面这行python代码:
sort_inds=[i[0] for i in sorted(enumerate(nums), key=lambda x:x[1])]
就表示元素排序之后，输出其对应的索引。
)
