时间戳

首页 > 解决方案 > 查找最大宽度“斜坡”（leetcode）

python - 查找最大宽度“斜坡”（leetcode）

问题描述

挑战如下：

给定一个整数数组 A，斜坡是一个元组 (i, j)，其中 i < j 且 A[i] <= A[j]。这种斜坡的宽度为 j - i。

求 A 中斜坡的最大宽度。如果不存在，则返回 0。

输入：[6,0,8,2,1,5] 输出：4 解释：最大宽度斜坡在 (i, j) = (1, 5) 处实现：A[1] = 0 和 A[5] = 5

我的代码：

class Solution:
    # maximum element
    # i = minimum element

    def maxWidthRamp(self, A: List[int]):
        max_count = 0
        for i in range(0, len(A)-1):
            for j in range(1 , len(A) - i):
                if A[i] <= A[i+j]:
                    if max_count < j:
                        max_count = j

        return max_count

嘿，我使用蛮力方法，在输出太大之前效果很好。我怎样才能使我的代码更加优化或者是否有其他方法可以更有效地解决这个问题？如果这样做，你能解释一下，因为我是初学者。

标签： python

解决方案

您可以使用按值顺序排序的索引列表以 O(NlogN) 而不是 O(N^2) 获得结果。

使用该排序的索引列表，您可以创建另外两个列表。一个用于最低的先前索引，一个用于最大的后续索引。

结合这两个列表将为您提供包含每个位置值的最大斜坡范围。

例如：

鉴于列表：

[9,8,1,0,1,9,4,0,4,1] # values
[0,1,2,3,4,5,6,7,8,9] # original indexes

排序位置的原始索引将是：

[3, 7, 2, 4, 9, 6, 8, 1, 0, 5] # of sorted values: [0, 0, 1, 1, 1, 4, 4, 8, 9, 9]

因为索引位置是按排序值排序的，所以在给定位置之后的任何索引都对应于 >= 该索引值的值。相反，位置之前的索引对应于 <= 该索引值的值。

因此，对于每个位置，最大斜坡范围介于最小的先前索引和最大的后续索引之间。

最小前面和最大后续索引将是：

[3, 3, 2, 2, 2, 2, 2, 1, 0, 0] # minimun preceding index
[9, 9, 9, 9, 9, 8, 8, 5, 5, 5] # maximum subsequent index

这建立了范围，我们通过最大值和最小值之间的差异获得每个排序位置的斜坡（范围大小）：

[3, 3, 2, 2, 2, 2, 2, 1, 0, 0] # minimun preceding
[9, 9, 9, 9, 9, 8, 8, 5, 5, 5] # maximum subsequent
[6, 6, 7, 7, 7, 6, 6, 4, 5, 5] # range sizes (difference), will select maximum

索引 2 到 9 的最大范围大小为 7（值：1 和 1）

您可以使用对 (index,value) 元组进行排序并从 itertools 中累积来实现这一点：

from itertools import accumulate

def maxRamp(a):
    ia = [ i for i,_ in sorted(enumerate(a),key=lambda x:x[1])]
    iMin = list(accumulate(ia,min))
    iMax = list(accumulate(ia[::-1],max))[::-1]
    i,j  = max(zip(iMin,iMax),key=lambda x:x[1]-x[0])
    return j-i

输出：

a = [9,8,1,0,1,9,4,0,4,1]
print(maxRamp(a)) # 7

b = [6,0,8,2,1,5]
print(maxRamp(b)) # 4

推荐阅读