用 Python 编写程序来查找最大宽度坡道

pythonserver side programmingprogramming更新于 2025/12/2 5:00:17

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

因此，如果输入为 nums = [6,0,8,2,1,5]，则输出将为 4，因为最大宽度斜坡在 (i, j) = (1, 5) 和 nums[1] = 0 和 nums[5] = 5 处实现。

为了解决这个问题，我们将遵循以下步骤 −

B := a new map
对于范围从 0 到 nums 大小的 i，执行
- x := nums[i]
- 如果 x 在 B 中，则
  - 在末尾插入 i B[x]
- 否则，
  - B[x] := [i]
mini := 一个列表，最初将一个 inf 存储到其中
maxi := 一个列表，最初将一个 -inf 存储到其中
对 B 的所有键的排序列表中的每个 x，执行
- 在 mini 的末尾插入 mini 的最后一个元素的最小值和 B[x] 的最小值
对 B 的所有键的反向排序列表中的每个 x，执行
- 插入 mini 的最后一个元素的最小值和 B[x] 的最小值在 mini 的末尾
maxi := 反转 maxi 然后从开始到倒数第二个元素获取子数组
mini := mini 的子数组[从索引 1 到末尾]
p := 0
res := -inf
当 p < 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))