# 4. Stack (7)
> 紀錄 NeetCode-150 與 LeetCode 的解題想法、刷題過程與錯誤，以 Python 或 C++ 兩種語言為主
>
> 其他 NeetCode-150 或 LeetCode 的主題請見 [Here](https://hackmd.io/-ovTFlzLRWaSgzDGhbSwsA)
<!-- 常用色碼紀錄
Easy: <font color="#00ad5f">**Easy**</font>
Medium: <font color="#ffbb00">**Medium**</font>
Hard: <font color="#ee2f56">**Hard**</font>
-->
##### Introduction
Stack 最大的特性是 Last-In-First-Out 性質，只要題目要求中有這個性質就可以考慮使用 stack 來做。
在 Python 中可使用 List 結構來模仿 stack 的操作，因為只能從其中一端增加(push)或刪除(pop)元素。可使用 List 結構的 `append()` 與 `pop()` 方法來模擬這兩種操作。
##### Momotomic stack
單調堆疊(monotonic stack)是一種特殊的 stack 結構，stack 中的元素會依照指定的順序儲存。根據不同的儲存順序可以再分為兩種不同形式：單調遞增堆疊(monotonic increasing stack)與單調遞減堆疊(monotomic decreasing stack)。
Monotonic stack 的結構常用在 finding the next greater element 或 find the next smaller element 的問題。
為了做到這種特殊結構的 stack，在進行 push 與 pop 運算時需要根據特定順序的需求來操作。
Monotonic increasing stack 指的是 stack 中的順序從底部(bottom)到頂端(top)會依照 (strictly) increasing 的順序排列，例如
$$
\text{Stack} = \{1,\ 3,\ 10,\ 15,\ 17\}
$$
Monotonic increasing stack 實作過程如下，視覺化過程可參考 [4]：
* 初始化一個空的 stack
* 迭代所有的元素，且對於每一個元素
* 當 stack 非空且頂端元素 > 目前元素時
* 彈出(pop)頂端元素，直到頂端元素 < 目前元素
* 推入(push)目前元素到 stack 中
* 迭代完後的 stack 就會保持 monotonic increasing 的順序
Monotonic decreasing stack 的過程與 increasing 類似，在此不贅述
Monotonic stack 的適用情境與問題如下：
* Find next greater element
* Find previous greater element
* Find maximum area hitogram
* Find maximum area in binary matrix
* Find sliding window maximum/minimum
##### Reference
關於 stack 的介紹可參閱以下資源
* [1] [Chap. 03 - Stack and Queue](/43igMpcvQbmbuGLH54_iJQ)
* [2] [What is Stack Data Structure? A Complete Tutorial](https://www.geeksforgeeks.org/introduction-to-stack-data-structure-and-algorithm-tutorials/?ref=gcse_outind)
* [3] [Stack Data Structure](https://www.geeksforgeeks.org/stack-data-structure/?ref=gcse_outind)
* [4] [Introduction to Monotonic Stack](https://www.geeksforgeeks.org/introduction-to-monotonic-stack-2/)
## 1. Valid Parentheses
<font color="#00ad5f">**Easy**</font>
> You are given a string `s` consisting of the following characters: ``'('``, ``')'``, ``'{'``, ``'}'``, ``'['`` and ``']'``.
>
> The input string `s` is valid if and only if:
>
> 1. Every open bracket is closed by the same type of close bracket.
> 2. Open brackets are closed in the correct order.
> 3. Every close bracket has a corresponding open bracket of the same type.
>
> Return `True` if s is a valid string, and `False` otherwise.
### Example 1:
```java
Input: s = "[]"
Output: true
```
### Example 2:
```java
Input: s = "([{}])"
Output: true
```
### Example 3:
```java
Input: s = "[(])"
Output: false
```
Explanation: The brackets are not closed in the correct order.
### Constraints
* `1 <= s.length <= 1000`
### Solution
#### 1. Brute force
不論題目給定的括號順序與類型如何，只要是合格的最內層就至少會有一組成對括號出現，例如 `({[][()]})` 中的成對為內部的最內層的 `()`。
依照提示，每次把一組同類型的括號(即最內層那組)取出，直到不能取出為止。如果取完後字串是空的即為 valid，反之有剩餘則為 inavlid。
```python=
# bruth force
class Solution:
def isValid(self, s: str) -> bool:
while ("()" in s) or ("[]" in s) or ("{}" in s):
s = s.replace("()", "")
s = s.replace("[]", "")
s = s.replace("{}", "")
if not s: # Empty string
return True
else: # Non empty string
return False
```
#### 2. Stack
以此題來說，題目括號的嵌套順序符合 stack 中 LIFO 的性質，越晚出現的 open bracket 對應的 close bracket 必須越早出現。
迭代的過程
* 遇到 open bracket 就堆疊到 stack 中
* 遇到 close bracket 時就把 stack 中的元素取出形成配對
因為越靠近 top 端的元素必定是越內層的符號，才能形成配對。在迭代過程中遇到 cose bracket 時也要注意
* 如果此時 stack 是空的，表示順序不對(由 close bracket 先開始)，是為 invalid
* 如果 close bracket 與 stack 頂端的 open bracket 不能形成配對，也是 invalid
最後迭代完字串後，stack 中的元素應該要是空的，才表示所有符號都能配對，如果 stack 非空表示有符號不能完成配對，是為 invalid。
另外，因為要做 open 與 close 的配對，所以還需要建立一個 hash map 來定義兩者的對應關係。
```python=
# stack version
class Solution:
def isValid(self, s: str) -> bool:
stack = []
bracketMapping = {")":"(", "]":"[", "}":"{"}
for ch in s:
# when meet close bracket
if ch in bracketMapping:
if stack and stack[-1] == bracketMapping[ch]:
stack.pop()
else:
return False
else:
stack.append(ch)
return True if not stack else False
```
## 2. Minimum Stack
<font color="#ffbb00">**Medium**</font>
> Design a stack class that supports the `push`, `pop`, `top`, and `getMin` operations.
>
> * `MinStack()` initializes the stack object.
> * `void push(int val)` pushes the element `val` onto the stack.
> * `void pop()` removes the element on the top of the stack.
> * `int top()` gets the top element of the stack.
> * `int getMin()` retrieves the minimum element in the stack.
>
> Each function should run in $O(1)$ time.
### Example 1:
```java
Input: ["MinStack", "push", 1, "push", 2, "push", 0,
"getMin", "pop", "top", "getMin"]
Output: [null,null,null,null,0,null,2,1]
Explanation:
MinStack minStack = new MinStack();
minStack.push(1);
minStack.push(2);
minStack.push(0);
minStack.getMin(); // return 0
minStack.pop();
minStack.top(); // return 2
minStack.getMin(); // return 1
```
### Constraints
* `-2^31 <= val <= 2^3`.
* `pop`, `top` and `getMin` will always be called on **non-empty** stacks.
### Solution
除了 `getMin()` 方法外，其他都是 stack 的基本操作，都可以在常數時間內完成。有問題的應該是 `getMin()` 方法。
#### 1. Brute force
最簡單的方法是必須看過一遍完整的 stack 來找到最小值，所以時間複雜度為 $O(n)$
```python=
class MinStack:
def __init__(self):
self.stack = []
def push(self, val: int) -> None:
self.stack.append(val)
def pop(self) -> None:
self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
m = self.stack[0]
for i in self.stack:
if m > i:
m = i
return m
```
#### 2. Two-stacks
為了在常數時間內找到最小值，勢必要犧牲部分的空間才能做到。因此，額外再內部在創建一個 stack，且這個額外的 stack 目的是用來儲存**任何時刻 main stack 中的最小值**
當 min stack 最 `pop` 運算時，extra stack 也跟著做 `pop`。但當 main stack 做 `push` 運算時，extra stack 需要注意以下幾點：
* 當 extra stack 為空時，`push` 新元素
* 當新元素小於 extra stack 頂端元素時，`push` 新元素
* 當 extra stack 頂端元素小於新元素時，再次 `push` extra stack 頂端元素，用以記錄該時刻 main stack 中的最小值
```python=
class MinStack:
def __init__(self):
self.stack = [] # main stack
self.minStack = [] # extra stack
def push(self, val: int) -> None:
self.stack.append(val)
if (not self.minStack) or (val <= self.minStack[-1]):
self.minStack.append(val)
else:
self.minStack.append(self.minStack[-1])
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]
```
## 3. Evaluate Reverse Polish Notation
<font color="#ffbb00">**Medium**</font>
> You are given an array of strings `tokens` that represents a **valid** arithmetic expression in **Reverse Polish Notation**.
>
> Return the integer that represents the evaluation of the expression.
>
> * The operands may be integers or the results of other operations.
> * The operators include `'+'`, `'-'`, `'*'`, and `'/'`.
> * Assume that division between integers always truncates toward zero.
### Example 1:
```java
Input: tokens = ["1","2","+","3","*","4","-"]
Output: 5
Explanation: ((1 + 2) * 3) - 4 = 5
```
### Constraints
* `1 <= tokens.length <= 1000`.
* tokens[i] is `'+'`, `'_'`, `'*'`, or `'/'`, or a string representing an integer in the range `[-100, 100]`.
### Solution
運算式的表示方式有三種，中序(infix)表示法、前序(prefix)表示法與後序(postfix)表示法。
中序表示法是我們一般書寫的習慣，運算子(operator)會放在兩個運算元(operand)之間。例如
$$
(((1 + 2) \times 3)-4)
$$
後序表示法會將運算子放在運算元之後。將中序表示法中運算子替換掉該層的右括號，再刪去左括號，即可得到後序表示法。以上述運算式為例，後序表示法為
$$
1\ 2 + 3 \times 4\ -
$$
前序表示法與後序表示法的寫法顛倒。此外前序表示法又稱為 Polish notation，因此此題要求的 reverse polish notation 就是後序表示法的意思。
後序表示法的計算是 Stack 的基本應用，資料結構中的介紹應該都會提到。在一串後序表示法的運算式中：
* 遇到運算元就做 push
* 遇到運算子就從 stack 中 pop 兩個元素出來做計算，計算後的結果再次 push 到 stack 中
```python=
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token == '+':
num2, num1 = stack.pop(), stack.pop()
stack.append(num1 + num2)
elif token == '-':
num2, num1 = stack.pop(), stack.pop()
stack.append(num1 - num2)
elif token == '*':
num2, num1 = stack.pop(), stack.pop()
stack.append(num1 * num2)
elif token == '/':
num2, num1 = stack.pop(), stack.pop()
stack.append(int(num1 / num2))
else:
stack.append(int(token))
return stack[0]
```
## 4. Generate Parentheses
<font color="#ffbb00">**Medium**</font>
> You are given an integer `n`. Return all well-formed parentheses strings that you can generate with `n` pairs of parentheses.
### Example 1:
```java
Input: n = 1
Output: ["()"]
```
### Example 2:
```java
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
```
You may return the answer in **any order**.
### Constraints
* `1 <= n <= 7`
### Solution
#### 1. Inspiration
回溯演算法(backtracking algorithm)通常用在歷遍所有的可能路徑來尋找問題的解答，類似窮舉法，當某條路徑無法繼續時就回溯到上一步探尋其他可能路徑。
Pseudo coade for backtracking：
```plaintext=
void FindSolution(parameters):
if (solution valid)
store the solution
return
for (all choice)
Apply(choice)
FindSolution(parameters)
BackTrack(remove choice)
return
```
#### 2. Backtracking
在這題中，可以使用 backtracking 把所有可能的結果都歷遍一次。根據題目需求可以整理出以下的條件限制
1. 需要有 n 個開括號`'('` 與 n 個閉括號 `')'`
2. 當閉括號 `')'` 的數量 < 開括號的數量時，才能添加閉括號 `')'`
3. 當開括號 `'('` 的數量 < n 時，才能添加開括號 `'('`
```python=
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
stack = [] # save probably solution
res = []
def backtrack(openNum, closeNum):
if openNum == closeNum == n:
res.append("".join(stack))
return
if openNum < n: # condition 3
stack.append("(")
backtrack(openNum+1, closeNum)
stack.pop() # back to previous path
if closeNum < openNum: # condition 2
stack.append(")")
backtrack(openNum, closeNum+1)
stack.pop() # back to previous path
backtrack(0,0) # initial condition
return res
```
## 5. Daily Temperature
<font color="#ffbb00">**Medium**</font>
> You are given an array of integers `temperatures` where `temperatures[i]` represents the daily temperatures on the `ith` day.
>
> Return an array `result` where `result[i]` is the number of days after the `ith` day before a warmer temperature appears on a future day. If there is no day in the future where a warmer temperature will appear for the `ith` day, set `result[i]` to `0` instead.
### Example 1:
```java
Input: temperatures = [30,38,30,36,35,40,28]
Output: [1,4,1,2,1,0,0]
```
### Example 2:
```java
Input: temperatures = [22,21,20]
Output: [0,0,0]
```
### Constraints
* `1 <= temperatures.length <= 1000`
* `1 <= temperatures[i] <= 100`
### Solution
#### 1. Monotonic stack
因為是要找下一個更高的溫度，類似 find next greater element 的問題，所以可以使用 monotonic stack 來解。
歷遍整個 array，當遇到較小的溫度時就以 (temperature, index) 的形式將其 push 到堆疊中，形成單調遞減(monotonic decreasing)的 stack。
遇到比 stack 頂端溫度還要大的數值，因為 push 後無法形成單調遞減的 stack，所以需先將頂端元素 pop 不斷移出，直到適合的大小順序後再將新元素插入。
此外，因為在 stack 中儲存的元素有包含 index，所以每 pop 移除元素時，就可以與當前欲插入的元素進行 index 的比較來計算過了多少天。
```python=
# monotonic stack
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
res = [0] * len(temperatures)
stack = [] # monotonic stack whose element is (temperature, idx)
for idx, temp in enumerate(temperatures):
while stack and temp > stack[-1][0]:
stackTemp, stackIdx = stack.pop()
res[stackIdx] = idx - stackIdx
stack.append([temp, idx])
return res
```
:::info
`res` 中儲存的是每個 index 遇到更大溫度所需要的天數，預測為 0
:::
## 6. Car Fleet
<font color="#ffbb00">**Medium**</font>
>There are `n` cars traveling to the same destination on a one-lane highway.
>
> You are given two arrays of integers `position` and `speed`, both of length `n`.
>
> * `position[i]` is the position of the ith car (in miles)
> * `speed[i]` is the speed of the `ith` car (in miles per hour)
>
> The **destination** is at position `target` miles.
>
> A car can **no** pass another car ahead of it. It can only catch up to another car and then drive at the same speed as the car ahead of it.
>
> A **car fleet** is a non-empty set of cars driving at the same position and same speed. A single car is also considered a car fleet.
>
> If a car catches up to a car fleet the moment the fleet reaches the destination, then the car is considered to be part of the fleet.
>
> Return the number of different **car fleets** that will arrive at the destination.
### Example 1:
```java
Input: target = 10, position = [1,4], speed = [3,2]
Output: 1
```
Explanation: The cars starting at 1 (speed 3) and 4 (speed 2) become a fleet, meeting each other at 10, the destination.
### Example 2:
```java
Input: target = 10, position = [4,1,0,7], speed = [2,2,1,1]
Output: 3
```
Explanation: The cars starting at 4 and 7 become a fleet at position 10. The cars starting at 1 and 0 never catch up to the car ahead of them. Thus, there are 3 car fleets that will arrive at the destination.
### Constraints
* `n == position.length == speed.length`.
* `1 <= n <= 1000`
* `0 < target <= 1000`
* `0 < speed[i] <= 100`
* `0 <= position[i] < target`
* All the values of `position` are **unique**.
### Solution
如圖所示，當兩條直線有交點時，表示兩車相遇(後車追上前車)，此時後車的速度會受到前車影響而放慢至與前車相同的速度。
當後車追上前車時，後車的速度會與前車相同，此時會與前車形成一個車隊(car fleet)，所以後車可以刪掉(pop)不看，只要看車隊的車頭是否抵達即可。
最後 stack 中有多少元素，就代表有幾台車隊的頭，就是有幾種車隊。
要注意的是 stack 中儲存的元素是每台車抵達終點的時間，因為要比較與前車的抵達時間，所以當 stack 元素大於 2 時才能開始比較，且是取後車(stack[-1])與前車(stack[-2])的抵達時間比較
```python=
# stack
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
pair = [(p, s) for p, s in zip(position, speed)]
pair.sort(reverse=True)
stack = [] # saved reach time
for p, s in pair:
stack.append((target - p) / s)
if len(stack) >= 2 and stack[-1] <= stack[-2]:
stack.pop()
return len(stack)
```
## 7. Largest Rectangle in Histogram
<font color="#ee2f56">**Hard**</font>
> You are given an array of integers `heights` where `heights[i]` represents the height of a bar. The width of each bar is `1`.
>
> Return the area of the largest rectangle that can be formed among the bars.
### Example 1:
```java
Input: heights = [7,1,7,2,2,4]
Output: 8
```
### Example 2:
```java
Input: heights = [1,3,7]
Output: 7
```
### Constraints
* `1 <= heights.length <= 1000`
* `0 <= heights[i] <= 1000`
### Solution
如下圖所示可以歸納出計算面積會有兩種方式
* 高度可以往右延伸來計算矩形面積
* 此時高度會形成遞增(increasing)的方式排列
* 且需要紀錄該段高度往左延伸的起點位置，這樣才能計算他對應的寬度
* 高度不可往右延伸，直接計算這個高度對應的面積
為此，我們需要把長條圖的高度依照遞增方式排序，所以在迭代過程中，當下一個高度比當前高度更低時，就將當前高度取出(pop)，直到形成遞增排序。
要注意的是，會發生 pop 的原因是因為下一個遇到比較低的高度，這個比較低的高度是可以往左延伸計算面積的，所以需要知道他往左延伸的邊界/起始值。事實上備取出(pop)的高度的 index 就是這個較低高度的左邊起始值。
```python=
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
maxArea = 0
stack = [] # pair: (startIdx, height)
for i, h in enumerate(heights):
start = i
while stack and stack[-1][1] > h:
index, height = stack.pop()
maxArea = max(maxArea, height * (i - index))
start = index
stack.append((start, h))
for i, h in stack:
maxArea = max(maxArea, h * (len(heights) - i))
return maxArea
```
Sign in with Wallet
Connect another wallet