# **程式筆記(stack)**
:::info
:information_source: 日期 : 2023/06/27
:::
**:thumbsup:** 絲路
取stack[-1]時，一定要檢查stack是否存在
跟前面的狀態有關，不能捨棄前面的東西(例如char / 數字) -> 用stack
**:thumbsup:** 基本
* Valid Parentheses
```
Input: s = "()[]{}"
Output: true
```
```python
class Solution:
def isValid(self, s: str) -> bool:
mapping = {")" : "(", "]" : "[", "}" : "{"}
stack = []
for c in s:
if c not in mapping.keys():
stack.append(c)
else:
if not stack or stack.pop() != mapping[c]:
return False
return True if not stack else False
```
* Remove All Adjacent Duplicates in String II
stack 紀錄 [c, count]
```
Input: s = "deeedbbcccbdaa", k = 3
Output: "aa"
Explanation:
First delete "eee" and "ccc", get "ddbbbdaa"
Then delete "bbb", get "dddaa"
Finally delete "ddd", get "aa"
```
```python
class Solution:
def removeDuplicates(self, s: str, k: int) -> str:
stack = [] # [c, count]
for c in s:
if stack and c == stack[-1][0]:
stack[-1][1] += 1
if stack[-1][1] == k:
stack.pop()
elif not stack or c != stack[-1][0]:
stack.append([c, 1])
res = ""
for c, count in stack:
res += c * count
return res
```
* Evaluate Reverse Polish Notation
逆波蘭表示法（Reverse Polish Notation, RPN）
遇到運算符才把前面「兩個」數字做運算
*a b 運算順序
```python
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for c in tokens:
if c not in "+-*/":
stack.append(int(c))
else:
a = stack.pop()
b = stack.pop()
if c == "+":
stack.append(b + a)
elif c == "-":
stack.append(b - a)
elif c == "*":
stack.append(b * a)
elif c == "/":
stack.append(int(b / a))
return stack[-1]
```
**:thumbsup:** 進階 : 前項運算
* Decode String
遇到"]"運算完，cur_c 更新成 pre_c + cur_c * n
```
Input: s = "3[a2[c]]"
Output: "accaccacc"
Example 3:
Input: s = "2[abc]3[cd]ef"
Output: "abcabccdcdcdef"
```
```python
class Solution:
def decodeString(self, s: str) -> str:
cur_n = 0
cur_c = ""
stack_c, stack_n = [], []
for c in s:
if c.isdigit():
cur_n = cur_n * 10 + int(c)
elif c == "[":
stack_n.append(cur_n)
cur_n = 0
stack_c.append(cur_c)
cur_c = ""
elif c.isalpha():
cur_c += c
elif c == "]":
n = stack_n.pop()
pre_c = stack_c.pop()
cur_c = pre_c + cur_c * n
return cur_c
```
* Basic Calculator II
用前一個opertor與cur number計算
```
ex. 10 - 4 + 5 * 6
1th round
c == "-"
cur_n = 10
oper = "+"
stack = [10]
update oper = c = "-"
2th round
c = "+"
cur_n = 4
oper = "-"
stack = [10, -4]
update oper = c = "+"
3th round
c = "*"
cur_n = 5
oper = "+"
stack = [10, -4, 5]
update oper = c = "*"
4th round
because of i == len(s) - 1
cur_n = 6
oper = "*"
5 * 6 = 30
stack = [10, -4, 30]
```
```python
class Solution:
def calculate(self, s: str) -> int:
stack = []
cur_n = 0
oper = "+"
for i, c in enumerate(s):
if c == " ":
pass
elif c.isdigit():
cur_n = cur_n * 10 + int(c)
if c in "+-*/" or i == len(s) - 1:
if oper == "+":
stack.append(cur_n)
elif oper == "-":
stack.append(-cur_n)
elif oper == "*":
pre_n = stack.pop()
stack.append(pre_n * cur_n)
elif oper == "/":
pre_n = stack.pop()
stack.append(int(pre_n / cur_n))
oper = c
cur_n = 0
return sum(stack)
```
* Asteroid Collision
用flag去紀錄
三種情況要持續用while檢查(每次撞擊完狀態會改變)，其中兩種情況可以不用繼續比較
```python
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
stack = []
flag = False
for a in asteroids:
flag = False
while stack and stack[-1] > 0 and a < 0:
if stack[-1] > abs(a):
flag = True
break
elif stack[-1] == abs(a):
flag = True
stack.pop()
break
elif stack[-1] < abs(a):
flag = False
stack.pop()
if not flag:
stack.append(a)
return stack
```
---
**:thumbsup:** **單調遞增/減 monotonic stack**
* Min Stack 找stack的最小值(要O(1))
額外創一個嚴格遞減minstack
*不能建立integer，因為刪掉最小min後，會需要次小min
```
push : 1 2 3
stack : [1, 2, 3]
min_stack : [1]
push : 3 2 1
stack : [3, 2, 1]
min_stack : [3, 2 ,1]
不須擔心min num不夠用 因為stack只會從最上往下刪
```
```python
# 基本版本 : 每個min num都占掉一個位置
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [float("inf")] # [num]
def push(self, val):
self.stack.append(val)
# no number / is smaller or same
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]
```
```python
# 優化版本 : 重複min num只占掉一個位置
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = [] # [num, count]
def push(self, val):
self.stack.append(val)
# no number / is smaller
if not self.min_stack or val < self.min_stack[-1][0]:
self.min_stack.append([val, 1])
# same number
elif val == self.min_stack[-1][0]:
self.min_stack[-1][1] += 1
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1][0]:
self.min_stack[-1][1] -= 1
if self.min_stack[-1][1] == 0:
del self.min_stack[-1]
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1][0]
```
* Daily Temperatures 找未來最高溫
嚴格遞減stack
```python
class Solution:
def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
stack = [] # [day, temp]
n = len(temperatures)
res = [0] * n
for i, t in enumerate(temperatures):
while stack and stack[-1][1] < t:
day, temp = stack.pop()
res[day] = i - day
stack.append([i, t])
return res
```
* Car Fleet 車車追逐
嚴格遞減stack
```
Input: target = 12, position = [10,8,0,5,3], speed = [2,4,1,1,3]
Output: 3
```
計算到終點的時間，如果前面那台車時間少(開快)，必能和後面時間多(開慢)的車撞到
```python
class Solution:
def carFleet(self, target: int, position: List[int], speed: List[int]) -> int:
record = []
for pos, speed in zip(position, speed):
record.append([pos, speed])
record.sort(key = lambda x : x[0])
stack = []
for pos, speed in record:
time = (target - pos) / speed
while stack and stack[-1] <= time:
stack.pop()
stack.append(time)
return len(stack)
```
**講解連結**
Provided by.
###### tags: `stack` `note` `code`
Sign in with Wallet
Connect another wallet