---
# System prepended metadata

title: '**程式筆記(stack)**'
tags: [code, stack, note]

---

# **程式筆記(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"
```

![image](https://hackmd.io/_uploads/ryU1-f_Z1x.png =90%x)

```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
![image](https://hackmd.io/_uploads/B1spyzubJe.png)

```
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
![image](https://hackmd.io/_uploads/S1_ZW2snT.png =70%x)

```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`