Greedy 策略: 最大化陣列距離 Max Distance in Arrays_Leetcode #624

Nadine Shaabana on Unsplash

題目敘述 624. Maximum Distance in Arrays

給定一個輸入二維陣列arrays。

陣列距離的定義 = max | a - b | 其中 a, b 來自不同的一維陣列

測試範例

Example 1:

Input: arrays = [[1,2,3],[4,5],[1,2,3]]
Output: 4
Explanation: 

Max distance = | 5 - 1 | = 4​

Example 2:

Input: arrays = [[1],[1]]
Output: 0

Max distance = | 1 - 1 | = 0

約束條件

Constraints:

• m == arrays.length

輸入陣列長度 = m

• 2 <= m <= 10^5

m 介於 2 ~ 十萬之間。

• 1 <= arrays[i].length <= 500

內部的一維陣列長度介於1~500

• -10^4 <= arrays[i][j] <= 10^4

每個陣列元素值介於 負一萬 ~ 正一萬

• arrays[i] is sorted in ascending order.

內部的一維陣列都是升序排列。

• There will be at most 10^5 integers in all the arrays.

輸入裡面，最多會有十萬個整數。

演算法 Greedy 策略: 最大化差值

distance = | a - b | 其中 a, b 來自不同的一維陣列

那就紀錄已經看過的最大值和最小值。

接著每回合針對當下的最小值和最大值做計算，取最大的差值。

候選人1: 已經看過的最大值 - 當下的最小值。

候選人2: 當下的最大值 -已經看過的最小值 。

接著更新distance 的最大值，選擇比較的大的那個候選人去做更新。

程式碼 Greedy 策略: 最大化差值

class Solution:
    def maxDistance(self, arrays):
        
        best = 0

        # Initialization
        cur_max, cur_min = -math.inf, math.inf

        for numbers in arrays:
            
            # Update max distance
            best = max(best, cur_max - numbers[0], numbers[-1] - cur_min  )

            # Update max value before, min value before
            cur_max, cur_min = max(cur_max, numbers[-1]), min(cur_min, numbers[0])
        
        return best

複雜度分析

時間複雜度: O(n)

依序處理每一個單獨的一維陣列，總共耗時O(n)。

空間複雜度: O(1)

所用到的變數都是臨時變數，所需空間為O(1)常數級別。

Refernce:

[1] Maximum Distance in Arrays - LeetCode