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

86會員
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
美國總統大選只剩下三天, 我們觀察一整週民調與金融市場的變化(包含賭局), 到本週五下午3:00前為止, 誰是美國總統幾乎大概可以猜到60-70%的機率, 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Thumbnail
Faker昨天真的太扯了,中國主播王多多點評的話更是精妙,分享給各位 王多多的點評 「Faker是我們的處境,他是LPL永遠繞不開的一個人和話題,所以我們特別渴望在決賽跟他相遇,去直面我們的處境。 我們曾經稱他為最高的山,最長的河,以為山海就是盡頭,可是Faker用他28歲的年齡...
 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
美國總統大選只剩下三天, 我們觀察一整週民調與金融市場的變化(包含賭局), 到本週五下午3:00前為止, 誰是美國總統幾乎大概可以猜到60-70%的機率, 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
Thumbnail
Faker昨天真的太扯了,中國主播王多多點評的話更是精妙,分享給各位 王多多的點評 「Faker是我們的處境,他是LPL永遠繞不開的一個人和話題,所以我們特別渴望在決賽跟他相遇,去直面我們的處境。 我們曾經稱他為最高的山,最長的河,以為山海就是盡頭,可是Faker用他28歲的年齡...
 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月寫這篇感想,港劇《溏心風暴》還在台灣電視上播出。