最大化兩組pair之間的差值 Max Product Diff Between Pairs Leetcode 1913
題目敘述
題目會給定一個整數陣列nums，要求我們找出兩組pair，分別是(a,b), 和 (c, d)，並且最大化 a*b - c * d 的值。
例如，給定 nums = [5,6,2,7,4]
那麼，最大的差值 = Max { a * b - c * d } = 7 * 6 - 2 * 4 = 34
測試範例
Example 1:
Input: nums = [5,6,2,7,4]
Output: 34
Explanation: We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.
Example 2:
Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.
約束條件
Constraints:
4 <= nums.length <= 10^41 <= nums[i] <= 10^4
演算法
第一直覺可能會想到先排序，再取最大的前兩個數字 和 最小的後兩個數字。
但是，其實不用排序。
這題其實換湯不換藥，和之前 最大兩數的乘積 Leetcode 1464 的概念是一樣的，都是在取極值(最大值或最小值)。
用演算法的角度想，就是貪婪Greedy的策略，只取最大值 和 最小值來做計算。
我們需要的只有前兩個最大的元素，和後兩個最小的元素。
造一個loop，從左到右掃描每個元素，
分別用兩個變數max_1, max_2去記錄最大值 和 第二大的值。
同理，用兩個變數min_1, min_2去記錄最小值 和 第二小的值。
最後，最大的兩項相乘 - 最小的兩項相乘
= max_1 * max_2 - min_1 * min_2 即為所求。
程式碼
class Solution:
def maxProductDifference(self, nums: List[int]) -> int:
# Initialization
min_1, min_2 = math.inf, math.inf
max_1, max_2 = -math.inf, -math.inf
# Greedy stragegy
# Select largest two numbers, as well as smaleest two numbers
# Max product difference = (max_1 * max_2) - (min_1 * min_2)
# Linear scan
for number in nums:
# update largest and sencond largest number
if number > max_1:
max_1, max_2 = number, max_1
elif number > max_2:
max_2 = number
# update smallest and sencond smallest number
if number < min_1:
min_1, min_2 = number, min_1
elif number < min_2:
min_2 = number
return max_1 * max_2 - min_1 * min_2
複雜度分析
時間複雜度:
O( n ) 一次從左到右的線性掃描，長度和原本的陣列一樣長。
空間複雜度:
O( 1 ) 使用到的是固定大小的臨時變數，所佔用空間為常數級別。
關鍵知識點
這題其實換湯不換藥，和之前 最大兩數的乘積 Leetcode 1464 的概念是一樣的，都是在取極值(最大值或最小值)。
陣列的輸入資料打散的前提下，當所求為前K大或前K小的元素時，
聯想到O(n)時間的線性掃描演算法。
不需要真的去排序，省下整個陣列排序的成本O(n log n)。
Reference:
[1] Python by greedy [ No sorting ] w/ comment - Maximum Product Difference Between Two Pairs - LeetCode
