付費限定
是否存在長度為3的遞增子序列 Increasing Triplet Subsequence_Leetcode 精選75題
閱讀時間約 3 分鐘
題目敘述
題目會給我們一個輸入陣列nums，要求我們判斷輸入陣列nums內部是否存在長度為三的遞增子序列?
測試範例
Example 1:
Input: nums = [1,2,3,4,5]
Output: true
Explanation: Any triplet where i < j < k is valid.
Example 2:
Input: nums = [5,4,3,2,1]
Output: false
Explanation: No triplet exists.
Example 3:
Input: nums = [2,1,5,0,4,6]
Output: true
Explanation: The triplet (3, 4, 5) is valid because nums[3] == 0 < nums[4] == 4 < nums[5] == 6.
約束條件
Constraints:
1 <= nums.length <= 5 * 10^5-2^31 <= nums[i] <= 2^31 - 1
演算法
這題是問存在與否，也就是找到一條長度為三的遞增子序列就算存在。
除了第一直覺的立方等級的暴力搜索演算法之外，其實還有一個更巧妙的O(n)線性時間演算法。
題目已經指定長度為三的遞增子序列，也就是說，抽象化的表達，可以這樣描述
Small, Medium, Large分別代表小、中、大三個元素，
其中 Small 小< Medium 中< Large 大。
一開始都初始化成無窮大，接著開始從左到右線性掃描，如果遇到比Small還小的數字，就更新 Small為更小的值。
同樣的道理，如果遇到比Small大但是比Medium還小的數字，就更新 Medium為更小的值。
最後，假如遇到比Small大也比Medium還大的數字，代表我們已經找到Large了，這時候，長度為三的遞增子序列分別就是Small, Medium和Large。
範例和概念示意圖:
image
以行動支持創作者！付費即可解鎖
本篇內容共 1451 字、1
則留言，僅發佈於Leetcode精選75題 解析+統整你目前無法檢視以下內容，可能因為尚未登入，或沒有該房間的查看權限。
86會員
425內容數
由有業界實戰經驗的演算法工程師，
手把手教你建立解題的框架，
一步步寫出高效、清晰易懂的解題答案。
著重在讓讀者啟發思考、理解演算法，熟悉常見的演算法模板。
深入淺出地介紹題目背後所使用的演算法意義，融會貫通演算法與資料結構的應用。
在幾個經典的題目融入一道題目的多種解法，或者同一招解不同的題目，擴展廣度，並加深印象。
留言0
查看全部
你可能也想看
Google News 追蹤
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
美國總統大選只剩下三天， 我們觀察一整週民調與金融市場的變化（包含賭局）， 到本週五下午3:00前為止， 誰是美國總統幾乎大概可以猜到60-70%的機率， 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
朋友们，大家好！今年是2024年了。两年前差不多也是这个时候，俄罗斯的军事行动正式开始，一直到现在，也看不出个什么结果来。中东现在也是战火连连。那么种种迹象，是否露出了第三次世界大战的苗头呢？现在，让我们来了解一下。
两年前，即2022年2月24日，俄罗斯开展了针对乌克兰的特别军事
詳細內容，請點擊觀賞→自由意志是一種虛擬的幻覺。自由意志是否存在？我們可以擺脫物理定律的因果關係嗎？
科學家逐漸發現到，時間與空間只是一種幻覺，現在連自由意志也是。
隨著科學的不斷進步，我們對自由意志的理解正經歷著一場顛覆性的變革。越來越多的科學實驗和研究似乎證實了一個令人深思的觀點：我們
圖片取自npr.org
只要是在歐美國家居住過的人，因該多多少少會接觸到所謂的"政治正確"。政治正確是近年來歐美國家所產生的一種意識，主要是針對種族和性別歧視的行為，包括言語侮辱、工資不對等、甚至種族犯罪。政治正確目前已具有極大的影響力，並為歐美國家在性別和種族平等上達到了很大的進步。同時，政治
許多人對於地球這顆行星的存在充滿了好奇，
對於人類能夠生存在地球上也提出了許多假設及研究，
但從古至今卻無人找到真正源頭及原因。
地球真正存在的原因，
人類的存在與外星種族是否有關聯，
這個答案要從人類為何存在於地球上講起。
在先前的影片[神明前身來歷與神界建立的緣由]中，
成功學是什麼？很多人說就是一門幫助我們成功的學問。我們要怎麼樣才可以邁向自己的成功呢？早期的成功學幾乎就是激勵課程，因為在當初的時代背景，很多人內心的壓抑不敢去挑戰，並且很多新的事物不敢去碰觸，所以當這些激勵課程出現的時候就能夠協助一些人勇敢突破。
來日本來得很匆忙，當時很想離開台灣好好度假，日文只學了五十音就來日本度假了，前三個月在大阪的語言學校念日語，為了減少開銷，找了一家台灣人開的民宿打工換宿。打工換宿挑的好，是很好的學習語言和旅行的方式，在民宿可以跟世界各地的背包客、日本上班族交流，尤其去過世界各地的背包客，旅行經驗豐富，來住民宿的
你有和朋友一起旅行過嗎？出遊如果過夜，晚上旅館訂同一個房間，這是極為常見的。只是，這不會發生在我身上。至少，有了夥伴至今，還沒發生過。
只要出門得過夜，如果室友不是家人，我絕對自己住。萬一是要跟朋友同一個房間的行程，像是露營或通鋪，我就直接不參加。
到底是有多少人怕這部電影暴雷呢？劇透似乎是很多人的禁忌，那麼這一次我就不談劇情內容細節，來談談這部《復仇者聯盟：終局之戰》帶給我的感受與想法，因為不是漫威迷，所以整個系列沒看過幾個，上次《復仇者聯盟：無限之戰》還是在成都看的，沒太多印象有沒有看過一和二。
這個秋，Chill 嗨嗨！穿搭美美去賞楓，裝備款款去露營⋯⋯你的秋天怎麼過？秋日 To Do List 等你分享！
秋季全站徵文，我們準備了五個創作主題，參賽還有機會獲得「火烤兩用鍋」，一起來看看如何參加吧～
美國總統大選只剩下三天， 我們觀察一整週民調與金融市場的變化（包含賭局）， 到本週五下午3:00前為止， 誰是美國總統幾乎大概可以猜到60-70%的機率， 本篇文章就是以大選結局為主軸來討論近期甚至到未來四年美股可能的改變
朋友们，大家好！今年是2024年了。两年前差不多也是这个时候，俄罗斯的军事行动正式开始，一直到现在，也看不出个什么结果来。中东现在也是战火连连。那么种种迹象，是否露出了第三次世界大战的苗头呢？现在，让我们来了解一下。
两年前，即2022年2月24日，俄罗斯开展了针对乌克兰的特别军事
詳細內容，請點擊觀賞→自由意志是一種虛擬的幻覺。自由意志是否存在？我們可以擺脫物理定律的因果關係嗎？
科學家逐漸發現到，時間與空間只是一種幻覺，現在連自由意志也是。
隨著科學的不斷進步，我們對自由意志的理解正經歷著一場顛覆性的變革。越來越多的科學實驗和研究似乎證實了一個令人深思的觀點：我們
圖片取自npr.org
只要是在歐美國家居住過的人，因該多多少少會接觸到所謂的"政治正確"。政治正確是近年來歐美國家所產生的一種意識，主要是針對種族和性別歧視的行為，包括言語侮辱、工資不對等、甚至種族犯罪。政治正確目前已具有極大的影響力，並為歐美國家在性別和種族平等上達到了很大的進步。同時，政治
許多人對於地球這顆行星的存在充滿了好奇，
對於人類能夠生存在地球上也提出了許多假設及研究，
但從古至今卻無人找到真正源頭及原因。
地球真正存在的原因，
人類的存在與外星種族是否有關聯，
這個答案要從人類為何存在於地球上講起。
在先前的影片[神明前身來歷與神界建立的緣由]中，
成功學是什麼？很多人說就是一門幫助我們成功的學問。我們要怎麼樣才可以邁向自己的成功呢？早期的成功學幾乎就是激勵課程，因為在當初的時代背景，很多人內心的壓抑不敢去挑戰，並且很多新的事物不敢去碰觸，所以當這些激勵課程出現的時候就能夠協助一些人勇敢突破。
來日本來得很匆忙，當時很想離開台灣好好度假，日文只學了五十音就來日本度假了，前三個月在大阪的語言學校念日語，為了減少開銷，找了一家台灣人開的民宿打工換宿。打工換宿挑的好，是很好的學習語言和旅行的方式，在民宿可以跟世界各地的背包客、日本上班族交流，尤其去過世界各地的背包客，旅行經驗豐富，來住民宿的
你有和朋友一起旅行過嗎？出遊如果過夜，晚上旅館訂同一個房間，這是極為常見的。只是，這不會發生在我身上。至少，有了夥伴至今，還沒發生過。
只要出門得過夜，如果室友不是家人，我絕對自己住。萬一是要跟朋友同一個房間的行程，像是露營或通鋪，我就直接不參加。
到底是有多少人怕這部電影暴雷呢？劇透似乎是很多人的禁忌，那麼這一次我就不談劇情內容細節，來談談這部《復仇者聯盟：終局之戰》帶給我的感受與想法，因為不是漫威迷，所以整個系列沒看過幾個，上次《復仇者聯盟：無限之戰》還是在成都看的，沒太多印象有沒有看過一和二。