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

閱讀時間約 3 分鐘

題目敘述 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

88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
發表第一個留言支持創作者!
題目敘述 860. Lemonade Change 假想一個經營檸檬水小舖的情境。 一杯檸檬水都賣$5 顧客付錢時只有三種可能,$5, $10 或 $ 20 初始時,檸檬水小舖沒有零錢。 給定一個顧客買檸檬水的付錢陣列bills,請問能不能滿足每一筆交易,並且找開零錢。 如果可以
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
題目敘述 149. Max Points on a Line 給定一串2維平面的點座標,請問最多有幾個點落在同一條直線上? 落在同一條直線也就是數學上所謂的"共線" colinear
題目敘述: 給定一個二維陣列的高與寬,並且給定起點位置座標。 請從起點位置開始順時針拜訪陣列元素,並且把沿路走過的座標記錄下來。 以陣列的形式返回答案。
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
題目敘述 860. Lemonade Change 假想一個經營檸檬水小舖的情境。 一杯檸檬水都賣$5 顧客付錢時只有三種可能,$5, $10 或 $ 20 初始時,檸檬水小舖沒有零錢。 給定一個顧客買檸檬水的付錢陣列bills,請問能不能滿足每一筆交易,並且找開零錢。 如果可以
題目敘述 Find K-th Smallest Pair Distance 給定一個輸入陣列nums和 參數k。 請找出第k小的pair distance是多少? pair distance定義為 abs( nums[i] - nums[j]), i 不等於j 也就是任意兩陣列元素差值的絕對值
題目敘述 Combination Sum II_Leetcode #40 給定一個整數陣列candidates 和 目標值target。 每個陣列元素只能選擇一次,請問有多少種組合方法,可以使得組合數總和 = target? 請把滿足組合數總和 = target的組合方法以陣列的形式返回答案
題目敘述 149. Max Points on a Line 給定一串2維平面的點座標,請問最多有幾個點落在同一條直線上? 落在同一條直線也就是數學上所謂的"共線" colinear
題目敘述: 給定一個二維陣列的高與寬,並且給定起點位置座標。 請從起點位置開始順時針拜訪陣列元素,並且把沿路走過的座標記錄下來。 以陣列的形式返回答案。
題目敘述 Integer to English Words 給定一個整數num 請轉換成對應的的英文數字表達(One, Two, Three, ... 那種數字表達式)
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
 When Greed Becomes Dominant: The Story Behind Cai Xia’s Speculation and Self-Stealing 1978 was the early stage of China's reform and opening up, a m
Thumbnail
漢來大飯店三麗鷗主題房住宿分享,搭配酷洛米主打歌 Greedy Greedy 金句名言思考人生。
Thumbnail
手作用品的善意與祝福,不只學會操作、思考,更能讓孩子因為「義賣」而更謹慎 每次手作課對孩子都是一次挑戰,因為看老師說明好像覺得沒什麼,但往往等到自己操作卻又覺得很驚恐:疑?怎麼會出錯? 不管是皮件設計還是烹飪,甚至是手工皂製作都是。孩子每次都在過程中激辯,似乎在回憶的過程中還要看誰的筆記更加詳細
Thumbnail
小樂30-電子股10檔 小樂30篩選方式 1.台灣上市櫃股票 2.產業龍頭、寡占地位或具備特殊利基的公司 3.近5年EPS大於1元 4.近5年現金股利大於1元 5.篩選30檔股票(傳產10檔/金融10檔/電子10 檔)
Thumbnail
小樂30-金融股 小樂30篩選方式 1.台灣上市櫃股票 2.產業龍頭、寡占地位或具備特殊利基的公司 3.近5年EPS大於1元 4.近5年現金股利大於1元 5.篩選30檔股票(傳產10檔/金融10檔/電子10 檔)
Thumbnail
小樂30-傳產股 小樂30篩選方式 1.台灣上市櫃股票 2.產業龍頭、寡占地位或具備特殊利基的公司 3.近5年EPS大於1元 4.近5年現金股利大於1元 5.篩選30檔股票(傳產10檔/金融10檔/電子10 檔) 傳產10檔: 本文為個人投資心得非投資建議,請注意風險盈虧自負!
Thumbnail
目前我的美股投資組合相對簡單,就是AAPL、SCM、QYLD這三檔,投資比重分別為27%、28%、45%。我的想法很簡單,就是拿SCM、QYLD每個月配發的股息來養AAPL。
Thumbnail
化學凝結的貓砂,貓咪吸入粉塵,那些化學粉塵就會停在貓咪肺部,無法化解,凝結成塊。造成隱性的慢性傷害。法國Greelys有機火山泥貓砂自然凝結、抗菌,除臭力又強,可以重複使用又不需要時常清理,尤其家裡有幼貓、老貓、病貓或傷貓的話,這款細緻天然、抗菌、無粉塵、不傷皮膚,又對貓咪身體有益的貓砂,真的很適合
Thumbnail
●2007港劇【溏心風暴1 Heart of Greed】安逸歡欣常在心(夏雨 李司棋 關菊英 米雪 陳豪 黃宗澤 林峯 楊怡 鍾嘉欣 蒙嘉慧 黎諾懿 陳法拉) 現在是2007年10月寫這篇感想,港劇《溏心風暴》還在台灣電視上播出。
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
 When Greed Becomes Dominant: The Story Behind Cai Xia’s Speculation and Self-Stealing 1978 was the early stage of China's reform and opening up, a m
Thumbnail
漢來大飯店三麗鷗主題房住宿分享,搭配酷洛米主打歌 Greedy Greedy 金句名言思考人生。
Thumbnail
手作用品的善意與祝福,不只學會操作、思考,更能讓孩子因為「義賣」而更謹慎 每次手作課對孩子都是一次挑戰,因為看老師說明好像覺得沒什麼,但往往等到自己操作卻又覺得很驚恐:疑?怎麼會出錯? 不管是皮件設計還是烹飪,甚至是手工皂製作都是。孩子每次都在過程中激辯,似乎在回憶的過程中還要看誰的筆記更加詳細
Thumbnail
小樂30-電子股10檔 小樂30篩選方式 1.台灣上市櫃股票 2.產業龍頭、寡占地位或具備特殊利基的公司 3.近5年EPS大於1元 4.近5年現金股利大於1元 5.篩選30檔股票(傳產10檔/金融10檔/電子10 檔)
Thumbnail
小樂30-金融股 小樂30篩選方式 1.台灣上市櫃股票 2.產業龍頭、寡占地位或具備特殊利基的公司 3.近5年EPS大於1元 4.近5年現金股利大於1元 5.篩選30檔股票(傳產10檔/金融10檔/電子10 檔)
Thumbnail
小樂30-傳產股 小樂30篩選方式 1.台灣上市櫃股票 2.產業龍頭、寡占地位或具備特殊利基的公司 3.近5年EPS大於1元 4.近5年現金股利大於1元 5.篩選30檔股票(傳產10檔/金融10檔/電子10 檔) 傳產10檔: 本文為個人投資心得非投資建議,請注意風險盈虧自負!
Thumbnail
目前我的美股投資組合相對簡單,就是AAPL、SCM、QYLD這三檔,投資比重分別為27%、28%、45%。我的想法很簡單,就是拿SCM、QYLD每個月配發的股息來養AAPL。
Thumbnail
化學凝結的貓砂,貓咪吸入粉塵,那些化學粉塵就會停在貓咪肺部,無法化解,凝結成塊。造成隱性的慢性傷害。法國Greelys有機火山泥貓砂自然凝結、抗菌,除臭力又強,可以重複使用又不需要時常清理,尤其家裡有幼貓、老貓、病貓或傷貓的話,這款細緻天然、抗菌、無粉塵、不傷皮膚,又對貓咪身體有益的貓砂,真的很適合
Thumbnail
●2007港劇【溏心風暴1 Heart of Greed】安逸歡欣常在心(夏雨 李司棋 關菊英 米雪 陳豪 黃宗澤 林峯 楊怡 鍾嘉欣 蒙嘉慧 黎諾懿 陳法拉) 現在是2007年10月寫這篇感想,港劇《溏心風暴》還在台灣電視上播出。