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

閱讀時間約 5 分鐘

題目敘述

題目會給定一個整數陣列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

52會員
336內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!