在 Python 中查找最大宽度斜坡的程序

假设我们有一个数组 nums，一个斜坡是一个元组 (i, j)，其中 i < j 并且 nums[i] <= nums[j]。这种斜坡的宽度是 (ji)。我们必须找到以 nums 为单位的斜坡的最大宽度。如果我们找不到这样的，则返回 0。

因此，如果输入类似于 nums = [6,0,8,2,1,5]，那么输出将为 4，因为最大宽度斜坡是在 (i, j) = (1, 5) 和 nums [1] = 0 和 nums[5] = 5。

示例

让我们看看以下实现以获得更好的理解 -

def solve(nums):
   B = {}
   for i in range(len(nums)):
      x = nums[i]
      if x in B:
         B[x].append(i)
      else:
         B[x] = [i]

   mini = [float('inf')]
   maxi = [float('-inf')]
   for x in sorted(B.keys()):
      mini.append(min(mini[-1], min(B[x])))

   for x in sorted(B.keys(), reverse = True):
      maxi.append(max(maxi[-1], max(B[x])))

   maxi = maxi[::-1][:-1]
   mini = mini[1:]

   p = 0
   res = float('-inf')
   while p < len(mini):
      res = max(res, maxi[p] - mini[p])
      p += 1

   return res

nums = [6,0,8,2,1,5]
print(solve(nums))

输入

[6,0,8,2,1,5]

4