付費限定

用 單調棧 來解 最近幾日股價的高點 Online Stock Span_Leetcode #901精選75題

閱讀時間約 6 分鐘

題目敘述

題目會給我們一個StockSpanner類別,
還有對應的建構子和function: int next( int price)介面。

next(int price)呼叫的時後回傳入當天的股票價格,要求我們計算price這個價格是過去k天以來的最高價,返回k值。

舉例來說:

若股價分別是[70, 50, 60]

則分別回傳1, 1, 2

70是過去一天以來{70}的最高價

50是過去一天以來{50}的最高價

60是過去兩天以來{50, 60}的最高價


題目的原文敘述


測試範例

Example 1:

Input
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output
[null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today's price of 75) were less than or equal to today's price.
stockSpanner.next(85); // return 6

約束條件

Constraints:

  • 1 <= price <= 10^5

參數price介於1~十萬之間。

  • At most 10^4 calls will be made to next.

動態測試時,最多有一萬次next() function呼叫。


演算法 Monotone Stack 單調棧


其實這題和前一題 每日溫度變化 Daily Temperatures 有異曲同工之妙,前一題是找之後比較大的值(之後比較溫暖的日子)這題是找能覆蓋前k天以來的數值(相當於說,今天的股價,是k天以來的最高點),背後的本值都時一樣的,都是盡可能的擴張區間,直到條件滿足為止


維護一個遞減單調棧,每次呼叫next() function推入今天股價時,把前面比較小的價格都pop出來,並且趁機計算能夠覆蓋的天數k值最後再把k值回傳即可。


範例 + 示意圖

以行動支持創作者!付費即可解鎖
本篇內容共 2570 字、1 則留言,僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容,可能因為尚未登入,或沒有該房間的查看權限。
avatar-img
88會員
425內容數
由有業界實戰經驗的演算法工程師, 手把手教你建立解題的框架, 一步步寫出高效、清晰易懂的解題答案。 著重在讓讀者啟發思考、理解演算法,熟悉常見的演算法模板。 深入淺出地介紹題目背後所使用的演算法意義,融會貫通演算法與資料結構的應用。 在幾個經典的題目融入一道題目的多種解法,或者同一招解不同的題目,擴展廣度,並加深印象。
留言0
查看全部
avatar-img
發表第一個留言支持創作者!
題目會給定一個輸入陣列temperatures ,分別代表每一天的溫度。 請計算每一天還要再過幾天才會遇到更溫暖的日子,如果遇不到,則回填0。 請以陣列的形式返回答案。 題目的原文敘述 約束條件 Constraints: 1 <= temperatures.length <= 10^
題目敘述 給定兩個字串word1和word2,每次操作時,可以有三個選項 插入一個字元 刪除一個字元 替換一個字元 請問把word1轉換成word2的最小操作次數是多少? 題目的原文敘述 約束條件 Constraints: 0 <= word1.length, word2.le
題目敘述 題目會給我們兩種無限量供應的骨牌Domino 和 Tromino,形狀分別如下 題目的輸入會有一個參數n。 可以任意旋轉方向進行拼接,請問最後拼成 2 x n 長方形區域的方法數有幾種? 例如 n = 3 時,拼成2 x 3 的長方形區域有五種方法。 題目的原文敘述
題目敘述 題目會給我們一個大樓陣列heights,裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目,和 ladders代表可用的伸縮爬梯數目。 一開始從最左邊的大樓頂樓開始出發。 假如下一棟比現在這棟大樓還矮,或者一樣高,則我們可以直接抵達下一棟。 假如下一棟比現在
題目敘述 題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 每次買入股票時會有一個額外附帶的交易成本fee。 題目讓我們做多,而且不限制交易次數。 題目禁止持有多重部位,也就是說,必須是買賣輪流交替的形式。 比如說 買,買,買 這種方式是不被允許的。 請問最終
題目敘述 題目會給我們泰伯納西數列的一般項和初始條件,要求我們實現找出第n項的function。 def tribonacci(self, n: int): 泰伯納西數列的一般項: Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. 泰伯納西數列的初始條件: T0 = 0,
題目會給定一個輸入陣列temperatures ,分別代表每一天的溫度。 請計算每一天還要再過幾天才會遇到更溫暖的日子,如果遇不到,則回填0。 請以陣列的形式返回答案。 題目的原文敘述 約束條件 Constraints: 1 <= temperatures.length <= 10^
題目敘述 給定兩個字串word1和word2,每次操作時,可以有三個選項 插入一個字元 刪除一個字元 替換一個字元 請問把word1轉換成word2的最小操作次數是多少? 題目的原文敘述 約束條件 Constraints: 0 <= word1.length, word2.le
題目敘述 題目會給我們兩種無限量供應的骨牌Domino 和 Tromino,形狀分別如下 題目的輸入會有一個參數n。 可以任意旋轉方向進行拼接,請問最後拼成 2 x n 長方形區域的方法數有幾種? 例如 n = 3 時,拼成2 x 3 的長方形區域有五種方法。 題目的原文敘述
題目敘述 題目會給我們一個大樓陣列heights,裡面分別記錄每一棟大樓的高度。還有參數bricks代表可用的磚塊數目,和 ladders代表可用的伸縮爬梯數目。 一開始從最左邊的大樓頂樓開始出發。 假如下一棟比現在這棟大樓還矮,或者一樣高,則我們可以直接抵達下一棟。 假如下一棟比現在
題目敘述 題目會給我們一個陣列prices,裡面的數值代表每一個交易日的股票股價。 每次買入股票時會有一個額外附帶的交易成本fee。 題目讓我們做多,而且不限制交易次數。 題目禁止持有多重部位,也就是說,必須是買賣輪流交替的形式。 比如說 買,買,買 這種方式是不被允許的。 請問最終
題目敘述 題目會給我們泰伯納西數列的一般項和初始條件,要求我們實現找出第n項的function。 def tribonacci(self, n: int): 泰伯納西數列的一般項: Tn+3 = Tn + Tn+1 + Tn+2 for n >= 0. 泰伯納西數列的初始條件: T0 = 0,
你可能也想看
Google News 追蹤
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
得到出乎意料之外的新年小禮物-一雙髒髒且受傷的手!牛仔褲實在太磨人了...
Thumbnail
圖說:2024台北電器空調影音3C電腦年終購物節,將於1/19~1/22台北世貿一館盛大開展。 【李婉如/ 報導】「2024台北電器空調影音 3C 電腦年終購物節」由中華民國電器商業同業公會全國聯合會、台北市電器商業同業公會共同主辦,將於1/19(五)~1/22(一)台北世貿一館隆重登場!匯集
Thumbnail
透過 Web Workers,您可以將這些耗時的操作放在另一個執行緒中處理,減輕主執行緒的負擔,提高網站的效能和響應速度。這篇文章提供了詳細的解釋和示例,幫助您快速上手使用 Web Workers。不要錯過這個可以改善網站效能的實用技巧!
Thumbnail
你的人生中,是否有一間曾讓你流連忘返的無菜單料理店呢? 如果你也對日式料理充滿興趣,又怕無菜單料理花了大錢卻踩到雷 就讓瑋威分享自己吃了四年的無菜單料理店 帶你一起體驗無菜單料理的魅力
Thumbnail
你/妳很常要重複註冊同一個產品嗎?也許這個方式會有幫助。
Thumbnail
📷📷​ 📷📷​ 隱士餐酒館The Hermit Bistro新竹店 距離火車新莊站騎車約五分鐘的距離 大門口動態投影屏幕很吸引路人目光走過很難不注意 📷📷​ 📷📷​ 📷📷​ 📷📷​ 動態投影呈現給人一種閒雲野鶴歸隱的俠客氣息 吧台區坐位有設計掛勾 和USB充電孔很貼心呢!
你眼中的攝影包應該是個什麼樣?記得在外出拍照時,筆者背著攝影包總會給人一種“一看就是玩攝影的”這樣的感覺。的確,市面上大多數攝影包的外觀設計都千篇一律,看起來總給人厚重之感,已經讓人審美疲勞瞭。不過樂攝寶Event Messenger系列則是個特例,近日這款Event Messenger 250單肩
黃偉哲請別用單一數據,掩飾你執政的無能 出動網軍、側翼秀下限,只為了蹭聲量?何必呢? 請問黃偉哲市長,當衛生局跟你說我們的疫苗剩餘率六都最少時,你別急著自嗨,更別出動支持者,側翼及網軍們特別幫你黃偉哲製圖po文,並四處散播讓人誤解的訊息!你這樣不就是最不要臉的網路蟑螂嗎? 1.六都第一疫苗剩餘率
「又變身了…」 看著鏡子裡變成多數人心目中英雄樣貌的自己,邱麟只覺得低落,沒有漫畫裡獲得力量的主角會有的興奮。 「以後你直接對著莉莉下達命令就行了,不管什麼都行,只要能讓他明白你是想要變成耀光就沒問題了。」 「以後…這真的不能拔掉嗎?」 「我說過了,除非你死。」 露西讓他站著不要動後,邱麟的面前突然
Thumbnail
從我第二次扭到腳,已經過了2星期。老師在體驗課上宣導生活四件事,就是這件事,我的執行率最高。腳現在已經不太痛了,來看看我做了什麼事吧!這個東西每個人家裡都有喔!
Thumbnail
這個秋,Chill 嗨嗨!穿搭美美去賞楓,裝備款款去露營⋯⋯你的秋天怎麼過?秋日 To Do List 等你分享! 秋季全站徵文,我們準備了五個創作主題,參賽還有機會獲得「火烤兩用鍋」,一起來看看如何參加吧~
Thumbnail
11/20日NVDA即將公布最新一期的財報, 今天Sell Side的分析師, 開始調高目標價, 市場的股價也開始反應, 未來一週NVDA將重新回到美股市場的焦點, 今天我們要分析NVDA Sell Side怎麼看待這次NVDA的財報預測, 以及實際上Buy Side的倉位及操作, 從
Thumbnail
Hi 大家好,我是Ethan😊 相近大家都知道保濕是皮膚保養中最基本,也是最重要的一步。無論是在畫室裡長時間對著畫布,還是在旅途中面對各種氣候變化,保持皮膚的水分平衡對我來說至關重要。保濕化妝水不僅能迅速為皮膚補水,還能提升後續保養品的吸收效率。 曾經,我的保養程序簡單到只包括清潔和隨意上乳液
Thumbnail
得到出乎意料之外的新年小禮物-一雙髒髒且受傷的手!牛仔褲實在太磨人了...
Thumbnail
圖說:2024台北電器空調影音3C電腦年終購物節,將於1/19~1/22台北世貿一館盛大開展。 【李婉如/ 報導】「2024台北電器空調影音 3C 電腦年終購物節」由中華民國電器商業同業公會全國聯合會、台北市電器商業同業公會共同主辦,將於1/19(五)~1/22(一)台北世貿一館隆重登場!匯集
Thumbnail
透過 Web Workers,您可以將這些耗時的操作放在另一個執行緒中處理,減輕主執行緒的負擔,提高網站的效能和響應速度。這篇文章提供了詳細的解釋和示例,幫助您快速上手使用 Web Workers。不要錯過這個可以改善網站效能的實用技巧!
Thumbnail
你的人生中,是否有一間曾讓你流連忘返的無菜單料理店呢? 如果你也對日式料理充滿興趣,又怕無菜單料理花了大錢卻踩到雷 就讓瑋威分享自己吃了四年的無菜單料理店 帶你一起體驗無菜單料理的魅力
Thumbnail
你/妳很常要重複註冊同一個產品嗎?也許這個方式會有幫助。
Thumbnail
📷📷​ 📷📷​ 隱士餐酒館The Hermit Bistro新竹店 距離火車新莊站騎車約五分鐘的距離 大門口動態投影屏幕很吸引路人目光走過很難不注意 📷📷​ 📷📷​ 📷📷​ 📷📷​ 動態投影呈現給人一種閒雲野鶴歸隱的俠客氣息 吧台區坐位有設計掛勾 和USB充電孔很貼心呢!
你眼中的攝影包應該是個什麼樣?記得在外出拍照時,筆者背著攝影包總會給人一種“一看就是玩攝影的”這樣的感覺。的確,市面上大多數攝影包的外觀設計都千篇一律,看起來總給人厚重之感,已經讓人審美疲勞瞭。不過樂攝寶Event Messenger系列則是個特例,近日這款Event Messenger 250單肩
黃偉哲請別用單一數據,掩飾你執政的無能 出動網軍、側翼秀下限,只為了蹭聲量?何必呢? 請問黃偉哲市長,當衛生局跟你說我們的疫苗剩餘率六都最少時,你別急著自嗨,更別出動支持者,側翼及網軍們特別幫你黃偉哲製圖po文,並四處散播讓人誤解的訊息!你這樣不就是最不要臉的網路蟑螂嗎? 1.六都第一疫苗剩餘率
「又變身了…」 看著鏡子裡變成多數人心目中英雄樣貌的自己,邱麟只覺得低落,沒有漫畫裡獲得力量的主角會有的興奮。 「以後你直接對著莉莉下達命令就行了,不管什麼都行,只要能讓他明白你是想要變成耀光就沒問題了。」 「以後…這真的不能拔掉嗎?」 「我說過了,除非你死。」 露西讓他站著不要動後,邱麟的面前突然
Thumbnail
從我第二次扭到腳,已經過了2星期。老師在體驗課上宣導生活四件事,就是這件事,我的執行率最高。腳現在已經不太痛了,來看看我做了什麼事吧!這個東西每個人家裡都有喔!