Python程式：查詢兩個數字列表中距離最大的配對

假設我們有兩個名為A和B的數字列表，它們的長度相同。我們需要找到所有0 ≤ i < j < n時：|a[i] - a[j]| + |b[i] - b[j]| + |i - j| 的最大值。

因此，如果輸入類似於A = [2, 4, 10, 6] B = [3, 4, 7, 5]，則輸出將為14，因為當i = 0且j = 2時，我們得到|2 - 10| + |3 - 7| + |1 - 3|。

為了解決這個問題，我們將遵循以下步驟：

  • ans := 0
  • n := a的長度
  • 對於每個配對 (s, t) in [(-1, -1) ,(-1, 1) ,(1, -1) ,(1, 1) ]，執行：
    • cur_min := 無窮大
    • cur_max := -無窮大
    • 對於 i in range 0 到 n，執行：
      • tmp := s * a[i] + t * b[i] + i
      • cur_min := cur_min 和 tmp 中的最小值
      • cur_max := cur_max 和 tmp 中的最大值
    • ans := ans 和 (cur_max - cur_min) 中的最大值
  • 返回 ans

讓我們看看下面的實現，以便更好地理解：

示例

 線上演示

class Solution:
   def solve(self, a, b):
      ans = 0
      n = len(a)
      for s, t in [(-1, -1), (-1, 1), (1, -1), (1, 1)]:
         cur_min = float("inf")
         cur_max = float("-inf")
         for i in range(n):
            tmp = s * a[i] + t * b[i] + i
            cur_min = min(cur_min, tmp)
            cur_max = max(cur_max, tmp)
            ans = max(ans, cur_max - cur_min)
      return ans
ob = Solution()
A = [2, 4, 10, 6]
B = [3, 4, 7, 5]
print(ob.solve(A, B))

輸入

[2, 4, 10, 6],[3, 4, 7, 5]

輸出

14

更新於: 2020年11月19日

127 次瀏覽

開啟你的職業生涯

透過完成課程獲得認證

開始學習
廣告