八. 栈和单调栈

普通栈：

剑指 Offer 09. 用两个栈实现队列

class CQueue:
    def __init__(self):
        self.A, self.B = [], []

    def appendTail(self, value: int) -> None:
        self.A.append(value)

    # 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈再删除。
    def deleteHead(self) -> int:
        if self.B: return self.B.pop()
        if not self.A: return -1
        while self.A:
            self.B.append(self.A.pop())
        return self.B.pop()


# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

20. 有效的括号

class Solution:
    def isValid(self, s: str) -> bool:
        if len(s) % 2 == 1: return False
        pairs = {'(':')','[':']','{':'}'}
        stack = list()
        # stack中存左括号。 如果是左括号， 加入栈中； 如果是右括号， 判断栈顶元素的键的值是否等于当前元素
        for c in s:
            if c in pairs:
                stack.append(c)
            elif not stack or pairs[stack.pop()] != c:
                return False
        return not stack

32. 最长有效括号

class Solution:
    def longestValidParentheses(self, s: str) -> int:
        if not s: return 0
        res = 0
        # stack一边匹配消消乐， 一边入栈
        # 这一步可以防止stack中匹配完为空时pop()报错
        stack = [-1]
        for i in range(len(s)):
            if s[i] == "(":
                stack.append(i)
            else:
                # 如果是右括号则出栈
                stack.pop()
                # 如果栈是空的话, 把右括号放进来
                if not stack: stack.append(i)
                # 当前全部数减去剩余无法配对的数（单身）即res
                else: res = max(res, i - stack[-1])
        return res

394. 字符串解码

class Solution:
    def decodeString(self, s: str) -> str:
        stack, res, multi = [], "", 0
        for c in s:
            if c == '[':
                stack.append([multi, res])
                res, multi = "", 0
            elif c == ']':
                cur_multi, cur_res = stack.pop()
                res = cur_res + cur_multi * res
            elif '0' <= c <= '9':
                multi = multi * 10 + int(c)            
            else:
                res += c
        return res
'''
if 数字， then 将数字转换为整数，用于后续倍数计算
if 字符， 延长当前字符串
if 左括号，当前状态压入栈
if 右括号，弹出状态，组合字符串
'''

150. 逆波兰表达式求值

class Solution:
    def evalRPN(self, tokens: List[str]) -> int:
        dict = {
            "+": add,
            "-": sub,
            "*": mul,
            "/": lambda x, y: int(x / y),   # 需要注意 python 中负数除法的表现与题目不一致
        }

        stack = list()
        for token in tokens:
            try:
                num = int(token)
            except ValueError:
                num2 = stack.pop()
                num1 = stack.pop()
                num = dict[token](num1, num2)
            finally:
                stack.append(num)
            
        return stack[0]

剑指 Offer 31. 栈的压入、弹出序列

class Solution:
    def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
        i = j = 0
        stack = []
        for i in range(len(pushed)):
            stack.append(pushed[i])
            while stack and stack[-1] == popped[j]:
                stack.pop()
                j += 1
        return not stack

剑指 Offer II 025. 链表中的两数相加

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        stack1, stack2 = deque([]), deque([])
        while l1:
            stack1.append(l1.val)
            l1 = l1.next
        while l2:
            stack2.append(l2.val)
            l2 = l2.next

        carry, p = 0, None
        while stack1 or stack2 or carry:
            num1 = stack1.pop() if stack1 else 0
            num2 = stack2.pop() if stack2 else 0
            ans = num1 + num2 + carry
            carry = ans // 10
            ans %= 10
            # 递归思想
            p = ListNode(ans, p)
        return p

单调栈：

155. 最小栈

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = [math.inf]

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

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(val)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()

739. 每日温度

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        stack, ans = [], [0] * len(temperatures)
        # 1.若栈为空或当日温度小于栈顶温度，则直接入栈
        # 2.若当日温度大于栈顶温度，说明栈顶元素升温日找到，将栈顶元素出栈，计算其与当日相差的天数
        for day, tmp in enumerate(temperatures):
            while stack and tmp > stack[-1][0]:
                stack_tmp, stack_day = stack.pop()
                ans[stack_day] = day - stack_day
            stack.append((tmp, day))
        return ans

84. 柱状图中最大的矩形

class Solution:
    def largestRectangleArea(self, heights: List[int]) -> int:
        stack = [-1]
        heights.append(0)
        n, ans = len(heights), 0
        for i in range(n):
            # 单调递增栈
            while stack and heights[i] < heights[stack[-1]]:
                p = stack.pop()
                l, r = stack[-1], i
                # 计算以栈顶元素勾勒出的最大面积
                ans = max(ans, heights[p] * (r - l - 1))            
            stack.append(i)
        return ans