Property of Stack:
- LIFO(Last in First Out)
- Common use case(In English): We need a container to keep track of previous state(we traversed already) so that as needed, we can efficiently access to this value. However, unlikely to array, we access that value by top of stack instead of index.
- 使用場景(In Chinese): 適用於需要一個container去記錄之前的狀態(we traversed already), 因為必要時我們需要去利用這個值. 但和array不同的是不能透過index 去access這個value, 而是利用top of stack去access這個value. 且通常top of stack 代表某個nearest/closest 的value to current moment. 而通常我們會想到用stack來解題, 是因為我們不在乎過去所有的狀態, 我們可能只在會比當前狀態小or大的時候的狀態的情況. For example, monotonic stack.(see LC 901. Online Stock Span as an example)
Monotone Stack/單調棧:
Here, I will try to summary what monotone stack is and why we can think about using monotone stack and how to use it in LC questions?
當我們只在乎們或是想找過去遍歷過的數據中, 比當前元素小的元素和那時候所對應的其他狀態.
Or
當我們只在乎們或是想找過去遍歷過的數據中, 比當前元素大的元素和那時候所對應的其他狀態.
就會想到用Monotone Stack
為了保持單調性，则每當加入一个新的元素時, 藉由與棧頂元素/top of stack/stack[-1]比較, 將棧中所有比當前元素小 or 大的數據全部出棧/pop.
Monotone Stack的應用, 可以利用單調棧求出以當前值为最大值或者最小值的連續子數组(continuous subarray)的最大長度(start index and end index)。(See LC 1856. Maximum Subarray Min-Product).
Note:
當題目有需要Sum of subarray, 馬上聯想到prefix sum 其中prefix sum需要start and end index to compute.
Note:
- 上面這系列stack題目跟過去狀態有關，所以這系列題目可能也跟DP有關.
- Amortized analysis(均攤分析)[3]: what amortized analysis is? Once you have a sequence of operations on a certain data structure, you try to estimate on average what time complexity is for those operations!!
The problem related to stack:
- 20. Valid Parentheses
- 739. Daily Temperatures
- 496. Next Greater Element I
- 503. Next Greater Element II
- 735. Asteroid Collision
- 394. Decode String
- 1249. Minimum Remove to Make Valid Parentheses
- 84. Largest Rectangle in Histogram
- 921. Minimum Add to Make Parentheses Valid
- 32. Longest Valid Parentheses
- 1856. Maximum Subarray Min-Product
Ref:
