最大化兩組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

85會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目敘述 題目會給我們一張Employee 資料表。裡面分別有employee_id、department_id 、primary_flag 等欄位。其中(employee_id, department_id) 是這張資料表的複合主鍵Primary key。 要求我們列出每一位員工的主要歸屬
題目敘述 題目會給我們一張Employees 資料表。裡面分別有employee_id、name、reports_to 、age 等欄位。其中employee_id 是這張資料表的主鍵Primary key。 要求我們列出每一位經理人下轄部屬的數量和部屬的平均年齡(四捨五入到最接近的整數)。
題目會給我們兩張資料表。 第一張是Customer資料表,裡面分別有customer_id 、product_key 等欄位。其中product_key 是這張資料表的外鍵foreign key,關連到第二張Product資料表。 題目還特別提醒,這張資料表可能包含重複的data row
題目敘述 題目會給定我們一顆二元搜索樹的根結點root,和任意兩個樹中的節點p和q。 要求我們找出p, q最靠近的公共祖先節點。 題目的原文敘述 測試範例 Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q
題目敘述 題目會給我們一張Courses資料表,裡面分別有student、class等欄位。其中(student, class) 是這張資料表的複合主鍵Primary key pair。 要求我們,以課程做分群,列出至少有五位同學的課程。 輸出的順序不拘。 Table: Courses
題目敘述 題目會給定我們一個二元矩陣grid,要求我們計算這個矩陣的Difference值,並且以矩陣的形式返回答案。 對於grid[i][j] 的Difference值定義 = 同一個row i裡面 1的數目 + 同一個column j裡面 1的數目 - 同一個row i裡面 0的數目
題目敘述 題目會給我們一張Employee 資料表。裡面分別有employee_id、department_id 、primary_flag 等欄位。其中(employee_id, department_id) 是這張資料表的複合主鍵Primary key。 要求我們列出每一位員工的主要歸屬
題目敘述 題目會給我們一張Employees 資料表。裡面分別有employee_id、name、reports_to 、age 等欄位。其中employee_id 是這張資料表的主鍵Primary key。 要求我們列出每一位經理人下轄部屬的數量和部屬的平均年齡(四捨五入到最接近的整數)。
題目會給我們兩張資料表。 第一張是Customer資料表,裡面分別有customer_id 、product_key 等欄位。其中product_key 是這張資料表的外鍵foreign key,關連到第二張Product資料表。 題目還特別提醒,這張資料表可能包含重複的data row
題目敘述 題目會給定我們一顆二元搜索樹的根結點root,和任意兩個樹中的節點p和q。 要求我們找出p, q最靠近的公共祖先節點。 題目的原文敘述 測試範例 Example 1: Input: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q
題目敘述 題目會給我們一張Courses資料表,裡面分別有student、class等欄位。其中(student, class) 是這張資料表的複合主鍵Primary key pair。 要求我們,以課程做分群,列出至少有五位同學的課程。 輸出的順序不拘。 Table: Courses
題目敘述 題目會給定我們一個二元矩陣grid,要求我們計算這個矩陣的Difference值,並且以矩陣的形式返回答案。 對於grid[i][j] 的Difference值定義 = 同一個row i裡面 1的數目 + 同一個column j裡面 1的數目 - 同一個row i裡面 0的數目
你可能也想看
Google News 追蹤
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
OKX 在12/13 有必嚕的 Jumpstart,依照目前市況估算5天大約5~10%報酬率,貓友可先閱讀此篇文章,本次直播將重點放在依據不同類型的貓友,如果最大化投資收益,分享重點如下: 挖BTC 池還是OKB 池? 對沖幣價波動的進階方法! 不同類型的貓友,該如何最大化投資收益
Thumbnail
Data-Driven Marketing 已成為行銷人必須掌握的關鍵手法。這種行銷模式是以客戶資料為基礎,透過數據分析來驅動行銷策略的製定和實施。這種模式讓我們能更精準地理解客戶需求,並最大化行銷效益。
Thumbnail
在繁華的城市中,小宅常被看作是對於居住舒適度的妥協,人們總認為小空間等同於擁擠和侷限。然而,室內設計的力量就在於此,它可以喚醒小宅的潛力,將其轉化為一個溫馨且功能強大的生活空間。本文將探討室內設計如何發掘小宅的潛力,並提供一些實用的設計建議。 相關文章:【室內設計解惑】什麼是現代簡約風?帶你領略簡約
Thumbnail
在現代化的高爾夫裡很重要的因素就是你的球速,而球速的主要來源在於你的擊球力量,當然力量的來源在你的身體整體的轉動速度和力量。我自己一直在研究身體力量要如何和你的球桿來配合,進而可以有一個最好、最穩定的擊球結果,而今天我想分享我的一些想法,大家也可以去思考這些點,看看能否讓你的擊球效果和質量有一些提升
你閱讀一個文章或者書本的時間,都安排多長呢? 我的閱讀預算,會在10, 25, 52分鐘三者做選擇。 並根據不同的閱讀時長,搭配不同的輸出目標。 具體來說,這些輸出目標是 10分鐘-淺閱讀 —> 輸出「為什麼我願意花時間看這個?」「這個講的東西可以怎麼融入我的日常?」兩個問題的答案。 25分鐘-中閱
Thumbnail
Potatomedia主要透過平台的回饋,加強與創作者的互動,不論是讀者還是創作者,也能從中得到收益,當你加入了Potatomedia之後,你會發覺多了一種動力,不論是寫作也好、點讚也好、留言也好,也能得到收入,這自然就會不自覺地去到處留言、點讚。
Thumbnail
你平常都是怎麼學習新知識的呢? 是坐在電腦或書桌前,利用1~2個小時的時間專心研究準備要學習的書或課程,還是在等公車的時候拿起手機看一下剛剛滑到的乾貨文? 現在因為社群媒體強大的傳播力,各種資訊唾手可得,再加上現在忙碌的生活步調,已經愈來愈難找到完整1~2個小時的時間了,也使得我們的學習逐漸碎片化
Thumbnail
來源:中油網站 請在週一時(回饋1.25%) 以中信御璽卡(回饋點數換算為0.8%) 儲值2000元到捷利卡(回饋5%) 再(不限週一)以捷利卡使用自助加油(回饋2.7%)消費 但中信點數消費30元得3點 每100點折8元 因此要拿到這裡的0.8%回饋 可待點數累積至1500點時 以「人工加油」使
Thumbnail
我任職的公司 GoFreight 不斷地成長後,多了不少管理層的角色,除了原本就有經驗的人以外,還有一些包括我在內的新手主管,對於管理其實沒有太多的經驗,剛好公司安排了管理課程內訓,讓管理新手有了不同的思維與看待管理這件事
Thumbnail
接下來第二部分我們持續討論美國總統大選如何佈局, 以及選前一週到年底的操作策略建議 分析兩位候選人政策利多/ 利空的板塊和股票
Thumbnail
🤔為什麼團長的能力是死亡筆記本? 🤔為什麼像是死亡筆記本呢? 🤨作者巧思-讓妮翁死亡合理的幾個伏筆
OKX 在12/13 有必嚕的 Jumpstart,依照目前市況估算5天大約5~10%報酬率,貓友可先閱讀此篇文章,本次直播將重點放在依據不同類型的貓友,如果最大化投資收益,分享重點如下: 挖BTC 池還是OKB 池? 對沖幣價波動的進階方法! 不同類型的貓友,該如何最大化投資收益
Thumbnail
Data-Driven Marketing 已成為行銷人必須掌握的關鍵手法。這種行銷模式是以客戶資料為基礎,透過數據分析來驅動行銷策略的製定和實施。這種模式讓我們能更精準地理解客戶需求,並最大化行銷效益。
Thumbnail
在繁華的城市中,小宅常被看作是對於居住舒適度的妥協,人們總認為小空間等同於擁擠和侷限。然而,室內設計的力量就在於此,它可以喚醒小宅的潛力,將其轉化為一個溫馨且功能強大的生活空間。本文將探討室內設計如何發掘小宅的潛力,並提供一些實用的設計建議。 相關文章:【室內設計解惑】什麼是現代簡約風?帶你領略簡約
Thumbnail
在現代化的高爾夫裡很重要的因素就是你的球速,而球速的主要來源在於你的擊球力量,當然力量的來源在你的身體整體的轉動速度和力量。我自己一直在研究身體力量要如何和你的球桿來配合,進而可以有一個最好、最穩定的擊球結果,而今天我想分享我的一些想法,大家也可以去思考這些點,看看能否讓你的擊球效果和質量有一些提升
你閱讀一個文章或者書本的時間,都安排多長呢? 我的閱讀預算,會在10, 25, 52分鐘三者做選擇。 並根據不同的閱讀時長,搭配不同的輸出目標。 具體來說,這些輸出目標是 10分鐘-淺閱讀 —> 輸出「為什麼我願意花時間看這個?」「這個講的東西可以怎麼融入我的日常?」兩個問題的答案。 25分鐘-中閱
Thumbnail
Potatomedia主要透過平台的回饋,加強與創作者的互動,不論是讀者還是創作者,也能從中得到收益,當你加入了Potatomedia之後,你會發覺多了一種動力,不論是寫作也好、點讚也好、留言也好,也能得到收入,這自然就會不自覺地去到處留言、點讚。
Thumbnail
你平常都是怎麼學習新知識的呢? 是坐在電腦或書桌前,利用1~2個小時的時間專心研究準備要學習的書或課程,還是在等公車的時候拿起手機看一下剛剛滑到的乾貨文? 現在因為社群媒體強大的傳播力,各種資訊唾手可得,再加上現在忙碌的生活步調,已經愈來愈難找到完整1~2個小時的時間了,也使得我們的學習逐漸碎片化
Thumbnail
來源:中油網站 請在週一時(回饋1.25%) 以中信御璽卡(回饋點數換算為0.8%) 儲值2000元到捷利卡(回饋5%) 再(不限週一)以捷利卡使用自助加油(回饋2.7%)消費 但中信點數消費30元得3點 每100點折8元 因此要拿到這裡的0.8%回饋 可待點數累積至1500點時 以「人工加油」使
Thumbnail
我任職的公司 GoFreight 不斷地成長後,多了不少管理層的角色,除了原本就有經驗的人以外,還有一些包括我在內的新手主管,對於管理其實沒有太多的經驗,剛好公司安排了管理課程內訓,讓管理新手有了不同的思維與看待管理這件事