栈

20. Valid Parentheses

class Solution:
    def isValid(self, s: str) -> bool:
        dic = {
            ')': '(',
            ']': '[',
            '}': '{'
        }
        stack = []
        for ch in s:
            if ch in dic:                           # 右括号
                if stack and stack[-1] == dic[ch]:
                    stack.pop()
                else:
                    return False
            else:                                   # 左括号
                stack.append(ch)
        return not stack

• 时间复杂度：
• 空间复杂度：

402. Remove K Digits

• 简化版：1673. Find the Most Competitive Subsequence

实际上是字典序的应用：对于两个不同的数字串，最靠左的不同的digit决定了两者大小；若要使得最后得到的数字串最小，则必须保证靠左的digit尽可能的小。

class Solution:
    def removeKdigits(self, num: str, k: int) -> str:
        remain = len(num) - k
        stack = []             # 非严格单调递增栈
        for digit in num:
            while k and stack and digit < stack[-1]:
                stack.pop()
                k -= 1
            stack.append(digit)
        return ''.join(stack[:remain]).lstrip('0') or '0'

• 时间复杂度：
• 空间复杂度：

739. Daily Temperatures

class Solution:
    def dailyTemperatures(self, temperatures: List[int]) -> List[int]:
        res = [0] * len(temperatures)
        stack = []  # 存放index的非严格单挑递减栈
        for i, T in enumerate(temperatures):
            while stack and T > temperatures[stack[-1]]:
                j = stack.pop()
                res[j] = i - j 
            stack.append(i)
        return res

• 时间复杂度：
• 空间复杂度：

232. Implement Queue using Stacks

class MyQueue:
    def __init__(self):
        self.A = []
        self.B = []
    def push(self, x: int) -> None:
        self.A.append(x)
    def pop(self) -> int:
        if not self.B:
            while self.A:
                self.B.append(self.A.pop())
        return self.B.pop()
    def peek(self) -> int:
        if self.B:
            return self.B[-1]
        else:
            return self.A[0]
    def empty(self) -> bool:
        return not self.A and not self.B

• 时间复杂度：pop() 和 peek() 操作都是均摊
• 空间复杂度：