最大化兩組pair之間的差值 Max Product Diff Between Pairs Leetcode 1913

Alex Radelich on Unsplash

題目敘述

題目會給定一個整數陣列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^4
• 1 <= 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