0.12 栈

[20. 有效的括号](https://leetcode.cn/problems/valid-parentheses/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def isValid(self, s: str) -> bool:
        dic = {'(':')','{':'}','[':']'}
        stack = []
        for item in s:
            if item in dic.keys():
                stack.append(item)
            else:
                if stack and dic[stack[-1]] == item:
                    stack.pop()
                else:
                    return False
        if len(stack) == 0:
            return True
        else:
            return False
```
[*155. 最小栈](https://leetcode.cn/problems/min-stack/?envType=study-plan-v2&envId=top-100-liked)
```py
class MinStack:
    def __init__(self):
        self.stack = []
        self.minstack = [inf]

def push(self, val: int) -> None:
        self.stack.append(val)
        self.minstack.append(min(self.minstack[-1], val))

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]
```
[*394. 字符串解码](https://leetcode.cn/problems/min-stack/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def decodeString(self, s: str) -> str:
        stack = []
        cur_res = ''
        cur_num = 0
        for c in s:
            if c == '[':
                stack.append([cur_num, cur_res])
                cur_num = 0
                cur_res = ''
            elif c == ']':
                pre_num, pre_res = stack.pop()
                cur_res = pre_res + pre_num * cur_res
            elif c.isdigit():
                cur_num = int(c) + cur_num * 10
            else:
                cur_res += c
        return cur_res
```
[*739. 每日温度](https://leetcode.cn/problems/daily-temperatures/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack = []
        n = len(temperatures)
        res = [0] * n
        for i in range(n):
            while stack and temperatures[i] > temperatures[stack[-1]]:
                j = stack.pop()
                res[j] = i - j
            stack.append(i)
        return res
```
[*84. 柱状图中最大的矩形](https://leetcode.cn/problems/largest-rectangle-in-histogram/?envType=study-plan-v2&envId=top-100-liked)
```py
class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        n = len(heights)
        stack = []
        max_area = 0
        for i in range(n+1):
            cur_height = heights[i] if i < n else 0
            # 单调递增栈
            while stack and cur_height < heights[stack[-1]]:
                top_idx = stack.pop()
                height = heights[top_idx]
                width = i if not stack else i - stack[-1] - 1
                max_area = max(max_area, height * width)
            stack.append(i)
        return max_area
```