962. Maximum Width Ramp
notruilin edited this page Mar 22, 2019
·
1 revision
二分是while (left < right),最后是left == right == ans,需要良好定义的区间 找 j-i 最大的一对数,使得i<j && A[i]<=A[j] 枚举j的位置,对于0到j-1维护一个下降序列d,对于每个j二分查找d中最靠前的小于等于A[j]的值
def binarySearch(d, x):
left = 0
right = len(d)
while (left < right):
mid = (left + right) / 2
if d[mid] > x:
left = mid + 1
else:
right = mid
if left == len(d):
return -1
else:
return left
实际有效区间应该是d[0]到d[len(d)-1],这里假设d[len(d)]是一个无穷小的值,如果不存在解,则left == right == len(d) 处理好边界不要加特判不要加特判不要加特判 另一种方法是按照A[x]的值对index进行排序,然后就直接比较index的差(循环中记录最小值即可):
def maxWidthRamp(self, A):
ans = 0
m = float('inf')
for i in sorted(range(len(A)), key = A.__getitem__):
ans = max(ans, i - m)
m = min(m, i)
return ans