↓快轉到主要內容

Monotonic-Stack

Stack 與單調棧
·3 分鐘
演算法 Stack Monotonic-Stack Greedy Simulation
巢狀結構解析、跟前一個元素合併的模擬、單調棧、貪心刪字元取字典序最小，以及 lazy deletion 的 Max Stack
LeetCode 4045: Count Robot Groups
·1 分鐘
LeetCode Medium Stack Monotonic-Stack Greedy
LeetCode 4045 解題筆記：先合併 t = 0 就夠近的機器人，再從右往左像車隊一樣，比前面車隊快的遲早會併入
LeetCode 1944: Number of Visible People in a Queue
·1 分鐘
LeetCode Hard Stack Monotonic-Stack
LeetCode 1944 解題筆記：從右往左維護遞減的單調棧，被彈出的都看得到，彈完剩下的那個也看得到
LeetCode 2355: Maximum Number of Books You Can Take
·2 分鐘
LeetCode Hard Dynamic-Programming Monotonic-Stack Stack Array
LeetCode 2355 解題筆記：以 i 結尾時往左每格少拿 1 本，直到碰到書比較少的瓶頸書架 j；用單調堆疊找 j，dp[i] = dp[j] + 等差數列和
LeetCode 316: Remove Duplicate Letters
·1 分鐘
LeetCode Medium Stack Monotonic-Stack Greedy String
LeetCode 316 解題筆記：單調棧 + 最後出現位置，頂端比較大而且後面還會出現就彈掉；已經在 stack 裡的直接跳過
LeetCode 1526: Minimum Number of Increments on Subarrays to Form a Target Array
·1 分鐘
LeetCode Hard Dynamic-Programming Greedy Monotonic-Stack Array
LeetCode 1526 解題筆記：從左往右看，每次比前一個高，多出來的高度都要新開那麼多次操作；變矮的部分可以沿用之前的操作
LeetCode 581: Shortest Unsorted Continuous Subarray
·1 分鐘
LeetCode Medium Two-Pointers Greedy Sorting Array Monotonic-Stack
LeetCode 581 解題筆記：從左往右記最大值，最後一個比最大值小的位置是右界；從右往左記最小值，最後一個比最小值大的位置是左界
LeetCode 3555: Smallest Subarray to Sort in Every Sliding Window
·1 分鐘
LeetCode Medium Two-Pointers Greedy Sorting Array Monotonic-Stack
LeetCode 3555 解題筆記：每個長度 k 的視窗都是一次 LeetCode 581；n 只有 1000，對每個視窗跑 O(k) 的兩次掃描即可
LeetCode 1793: Maximum Score of a Good Subarray
·1 分鐘
LeetCode Hard Two-Pointers Greedy Binary-Search Array Monotonic-Stack
LeetCode 1793 解題筆記：從 k 往兩邊擴張，每次往鄰居比較大的那一邊走，讓每個長度的最小值盡量大；到邊界時只能往另一邊
LeetCode 1574: Shortest Subarray to be Removed to Make Array Sorted
·1 分鐘
LeetCode Medium Two-Pointers Binary-Search Array Monotonic-Stack
LeetCode 1574 解題筆記：留下來的一定是「非遞減前綴 + 非遞減後綴」；先找出最長前綴和後綴，再用雙指針把兩段接起來
LeetCode 3816: Lexicographically Smallest String After Deleting Duplicate Characters
·1 分鐘
LeetCode Hard Stack Monotonic-Stack Greedy String
LeetCode 3816 解題筆記：單調棧，頂端比較大而且還有別的副本就刪；最後把尾巴重複的也刪掉，因為前綴一定比較小
LeetCode 901: Online Stock Span
·1 分鐘
LeetCode Daily Medium Stack Monotonic-Stack Data-Structures Design Design-Patterns Stock
使用單調堆疊解決股票價格跨度問題