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

假设我们有一个数组 nums，一个坡道是一个元组 (i, j)，其中 i < j 且 nums[i] <= nums[j]。这种坡道的宽度是 (j-i)。我们要在 nums 中找到最大的坡道宽度。如果我们找不到这样的坡道，则返回 0。

因此，如果输入是 nums = [6,0,8,2,1,5]，则输出将是 4，因为最大的坡道宽度是在 (i，j) 之间实现的，其中 (i，j) = (1，5)，并且 nums[1] = 0，nums[5] = 5。

要解决这个问题，我们将按照以下步骤执行：

B := 一个新的映射
对于范围在 nums 大小内的 i，执行以下操作 –
- x := nums[i]
- 如果 x 在 B 中，则
  - 在 B[x] 的末尾插入 i
- 否则，
  - B[x] := [i]
mini := 一个列表，最初将一个 inf 存储到其中
maxi:= 一个列表，最初将一个 -inf 存储到其中
对于所有键的列表排序得到的所有 x，请执行以下操作 –
- 在 mini 的末尾插入 mini 的最后一个元素和 B[x] 的最小值
对于所有键的逆向排序得到的所有 x，请执行以下操作 –
- 在 maxi 的末尾插入 maxi 的最后一个元素和 B[x] 的最大值
maxi:= 反转 maxi，然后从第一个元素开始取子数组到倒数第二个元素
mini := mini 的子数组[从索引 1 到结尾]
p := 0
res := -inf
while p < len(mini)，执行以下操作 –
- res := res 和 (maxi[p] – mini[p]) 的最大值
- p := p + 1
返回 res

例子

让我们看以下实现以更好地理解 –

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))