Python程式：查詢最大寬度斜坡

假設我們有一個數組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 := 一個新的對映

  • 對於範圍從0到nums大小的i，執行：

    • x := nums[i]

    • 如果x在B中，則

      • 將i插入B[x]的末尾

    • 否則，

      • B[x] := [i]

  • mini := 一個最初儲存一個無窮大的列表

  • maxi := 一個最初儲存一個負無窮大的列表

  • 對於B的所有鍵的排序列表中的每個x，執行：

    • 將mini的最後一個元素的最小值和B[x]的最小值插入mini的末尾

  • 對於B的所有鍵的反向排序列表中的每個x，執行：

    • 將mini的最後一個元素的最小值和B[x]的最小值插入mini的末尾

  • maxi := 反轉maxi，然後取從開始到倒數第二個元素的子陣列

  • mini := mini[從索引1到末尾]的子陣列

  • p := 0

  • res := 負無窮大

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

輸入

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

輸出

4

更新於：2021年10月6日

253 次瀏覽

開啟您的職業生涯

完成課程獲得認證

開始學習
廣告