# * T(n) S(1)
class Solution:
  def maxProfit(self, prices: List[int]) -> int:
    # * maxSale[i]表示在第i天买入，后续卖出的最大价格
    # * 也就是i右边prices的最大值
    n = len(prices); maxSale = [0 for _ in range(n)]
    running = 0
    res = 0
    # * 倒序滚动计算
    # * 最后一天卖不出去，必然是0，跳过计算
    for i in range(n - 2, -1, -1):
      # * i右边区间最大值
      running = max(running, prices[i + 1])
      maxSale[i] = running
      # * 得到后立刻可用当前位置i价格减去maxSale[i]得到收益
      # * 可以同时滚动计算最大收益
      res = max(res, maxSale[i] - prices[i])
    return res

# * 三句话拿下跳跃游戏
# * T(n) S(1)
class Solution:
  def canJump(self, nums: List[int]) -> bool:
    # * 为了不做特判，初始化能走的距离为1
    # * 相当于从-1先走到0，确保第一个走必然可执行
    n = len(nums); canWalk = 1
    for i in range(n):
      # * 更新最大可走距离
      canWalk = max(canWalk - 1, nums[i])
      # * 如果从这走得到结尾
      if i + canWalk >= n - 1: return True
      # * 如果在这走不动了，就到不了
      if canWalk == 0: return False

# * T(n) S(1)
class Solution:
  def climbStairs(self, n: int) -> int:
    # * 0为起点没有方案
    # * 1有1种
    # * 循环数组
    dp = [0, 1]
    for i in range(n):
      # * 来源于前一或前二
      dp[(i + 2) % 2] = dp[(i + 1) % 2] + dp[i % 2]
    # * 代入最后 i = n - 1
    return dp[(n + 1) % 2]

# * T(n^2) S(1)
class Solution:
  def generate(self, numRows: int) -> List[List[int]]:
    # * dp初值
    res = [[1]]
    # * 去掉第一个
    for i in range(2, numRows + 1):
      # * 只计算中间部分，去掉首尾1
      n = len(res[-1])
      layer = [1]
      # * 每次取上层的对应位置与前一位置（取模）求和
      for j in range(1, i - 1):
        layer.append(res[-1][j % n] + res[-1][(j - 1) % n])
      # * 拼接尾部1
      layer.append(1)
      # * 加入结果
      res.append(layer)
    return res

# * T(n) S(1)
class Solution:
  def rob(self, nums: List[int]) -> int:
    # * 依赖前两位状态，大小为2的循环数组
    dp = [0, 0]; n = len(nums)
    for i in range(n):
      # * 不拿与拿 取最大
      dp[(i + 2) % 2] = max(dp[(i + 1) % 2], dp[i % 2] + nums[i])
    return dp[(n - 1) % 2]

# * 完全背包 - 当和恰好n时最小结果
# * T(n^1.5) S(n)
class Solution:
  def numSquares(self, n: int) -> int:
    # * 只来源于上一个状态与当前状态，1维
    # * 求最小，初始化inf   n不为0，和为0的数量为0
    dp = [inf for _ in range(n + 1)]; dp[0] = 0
    
    # * 考虑到数字i 求和为c
    # * 原则上 n开平方操作可以快速幂，logn (!)
    for i in range(1, int(n ** 0.5) + 1):
      cur = i * i
      # * 逆对角线正向算
      # * cur之前不修改，同一个数组，等价于来源于上一个i
      for c in range(cur, n + 1):
        dp[c] = min(dp[c], dp[c - cur] + 1)
    
    return dp[n]

# * 完全背包 - 当和恰好n时最小结果
# * T(len(coins) * amount) S(amount)
class Solution:
  def coinChange(self, coins: List[int], amount: int) -> int:
    # * 同上一题
    dp = [inf for _ in range(amount + 1)]; dp[0] = 0

    for v in coins:
      for c in range(v, amount + 1):
        dp[c] = min(dp[c], dp[c - v] + 1)
    
    return dp[amount] if dp[amount] != inf else -1

# * 连通分量问题 - 并查集
# * T(mn) S(mn)
class Solution:
  def numIslands(self, grid: List[List[str]]) -> int:
    m = len(grid); n = len(grid[0])
    # * 每一点的编号为数组展开后的下标
    father = [i for i in range(m * n)]
    # * 并查集模板
    def find(u):
      if father[u] != u:
        father[u] = find(father[u])
      return father[u]
    def join(u, v):
      u = find(u)
      v = find(v)
      if u == v: return
      father[u] = v
    # * 遍历为1的地图点
    # * 将其与上方和左方相连接
    for i in range(m):
      for j in range(n):
        if grid[i][j] == '0': continue
        # * 按照遍历顺序，要么与上方join，要么与左方join
        # * 至少有一个连接方向
        if i > 0 and grid[i - 1][j] == '1': join(i * n + j, (i - 1) * n + j) 
        if j > 0 and grid[i][j - 1] == '1': join(i * n + j, i * n + j - 1)
    # * 压缩路径后 统计连通分量数
    connected = set()
    for i in range(m):
      for j in range(n):
        if grid[i][j] == '0': continue
        find(i * n + j)
        connected.add(father[i * n + j])
    return len(connected)

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

# * T(m + n) S(1)
class Solution:
  def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> Optional[ListNode]:
    # * 观察可得，如果让较长的链表先走
    # * 走过与较短的链表作差的长度
    # * 可以使二者相对于交点的距离相同
    # * 这样同时出发就可以在交点相遇
    
    # * 求长度
    def getLength(head):
      cnt = 0
      while head:
        head = head.next
        cnt += 1
      return cnt
    lA = getLength(headA)
    lB = getLength(headB)
    # * 长的走过相差值
    if lA > lB:
      for _ in range(lA - lB):
        headA = headA.next
    else:
      for _ in range(lB - lA):
        headB = headB.next
    # * 同时走直至相遇
    while headA and headB:
      if headA is headB:
        return headA
      headA = headA.next
      headB = headB.next
    # * 不相遇没有交点
    return None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(n) S(1)
class Solution:
  def reverseList(self, head: Optional[ListNode]) -> Optional[ListNode]:
    pre = None
    cur = head
    while cur:
      nxt = cur.next
      cur.next = pre
      pre = cur
      cur = nxt
    return pre

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(n) S(1)
class Solution:
  def reverseBetween(self, head: Optional[ListNode], left: int, right: int) -> Optional[ListNode]:
    p0 = dummy = ListNode(0, head)
    for _ in range(left - 1): p0 = p0.next
    pre = None
    cur = p0.next
    for _ in range(right - left + 1):
      nxt = cur.next
      cur.next = pre
      pre = cur
      cur = nxt
    # * 两次头到尾
    p0.next.next = cur
    p0.next = pre
    return dummy.next    

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(n) S(1)
class Solution:
  def isPalindrome(self, head: Optional[ListNode]) -> bool:
    # * 反转后半之后一一比对即可
    
    # * 找中点
    slow = fast = head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
    
    # * 反转后半
    pre = None
    cur = slow
    while cur:
      nxt = cur.next
      cur.next = pre
      pre = cur
      cur = nxt
    
    # * 比对
    while pre: 
      if pre.val != head.val: return False
      pre = pre.next; head = head.next
    
    return True    

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# * T(n) S(1)
# * 相遇慢指针走不完一圈
class Solution:
  def hasCycle(self, head: Optional[ListNode]) -> bool:
    slow = fast = head
    # * 要访问fast.next.next 需要 fast.next 不为空
    # * 要fast.next 不为空 需要 fast 不为空
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow is fast: return True
    return False

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(n) S(1)
class Solution:
  def middleNode(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    # * fast偶数长度在空 奇数下一个为空 
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
    return slow

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None
# * T(n) S(1)
# * 起点到入口 a
# * 入口到相遇 b
# * 相遇到入口 c
# * 当slow与fast相遇：2倍慢走2(a + b) = 快走a + b + k(b + c)
# * a - c = (k - 1)(b + c)
# * 若此时head从起点走c步，剩余到入口为a-c恰好为k-1倍环长
# * 若slow同步走，恰好走到入口，所以当slow与head相遇时即找到入口

# * 追赶速度为1追赶距离为环长-1，slow与fast相遇T(n)
# * 之后head从头走到入口 T(n)
# * 合计T(n)
class Solution:
  def detectCycle(self, head: Optional[ListNode]) -> Optional[ListNode]:
    slow = fast = head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
      if slow is fast:
        while head is not slow:
          head = head.next
          slow = slow.next
        return slow
    return None

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * 链表归并 与归并排序的一部分逻辑等同
# * T(m + n) S(1)
class Solution:
  def mergeTwoLists(self, list1: Optional[ListNode], list2: Optional[ListNode]) -> Optional[ListNode]:
    # * 建立虚拟节点，这样每次修改都是上一个节点
    # * 读取却是从下一个节点开始，不会冲突
    dummy = ListNode(0)
    cur = dummy
    # * 共有部分，每次选一个
    while list1 and list2:
      if list1.val < list2.val: cur.next = list1; list1 = list1.next
      else: cur.next = list2; list2 = list2.next
      cur = cur.next
    # * 剩余直接拼接
    if list1: cur.next = list1 
    if list2: cur.next = list2
    return dummy.next

# # Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * 找中间节点，反转后半
# * 交替更新
# * T(n) S(1)
class Solution:
  def reorderList(self, head: Optional[ListNode]) -> None:
    """
    Do not return anything, modify head in-place instead.
    """
    # * 找中间节点
    slow = fast = head
    while fast and fast.next:
      slow = slow.next
      fast = fast.next.next
    mid = slow
    # * 反转后半
    pre = None
    cur = mid
    while cur:
      nxt = cur.next
      cur.next = pre
      pre = cur
      cur = nxt
    # * 交替更新
    head2 = pre
    while head2.next:
      nxt = head.next
      nxt2 = head2.next
      head.next = head2
      head2.next = nxt
      head = nxt
      head2 = nxt2

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(m + n) S(1)
class Solution:
  def addTwoNumbers(self, l1: Optional[ListNode], l2: Optional[ListNode]) -> Optional[ListNode]:
    # * 进位
    carry = 0
    cur = dummy = ListNode(0)
    # * 处理公共部分
    while l1 and l2:
      v = l1.val + l2.val + carry
      if v >= 10: carry = 1; v -= 10
      else: carry = 0
      cur.next = ListNode(v)
      cur = cur.next; l1 = l1.next; l2 = l2.next
    # * 处理剩余部分
    while l1:
      v = l1.val + carry
      if v >= 10: carry = 1; v -= 10
      else: carry = 0
      cur.next = ListNode(v)
      cur = cur.next; l1 = l1.next
      
    while l2:
      v = l2.val + carry
      if v >= 10: carry = 1; v -= 10
      else: carry = 0
      cur.next = ListNode(v)
      cur = cur.next; l2 = l2.next
      
    if carry: cur.next = ListNode(carry)
    
    return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(n) S(1)
class Solution:
  def removeNthFromEnd(self, head: Optional[ListNode], n: int) -> Optional[ListNode]:
    # * 12345
    # * n = 2
    # * 012345
    # * 3 6
    # * 0 3
    # * 考虑到可能删除头结点的情况，需要建立虚拟节点
    slow = fast = dummy = ListNode(0, head)
    # * 在虚拟节点基础上快指针先走n + 1步，因为要删除需要得到其前一个节点
    while fast and n + 1:
      fast = fast.next; n -= 1
    # * 走不完n + 1步，不存在可删除元素
    if n + 1 != 0: return None
    # * 同时前行，使得慢指针恰好成为待删除元素的前一个元素
    while fast: slow = slow.next; fast = fast.next
    # * 删除
    slow.next = slow.next.next
    # * 返回
    return dummy.next

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next
# * T(n) S(1)
class Solution:
  def reverseKGroup(self, head: Optional[ListNode], k: int) -> Optional[ListNode]:
    p0 = dummy = ListNode(0, head)
    cur = head; n = 0
    while cur: cur = cur.next; n += 1
    pre = None
    cur = p0.next
    while n >= k:
      n -= k
      for _ in range(k):
        nxt = cur.next
        cur.next = pre
        pre = cur
        cur = nxt
      # * 迭代
      nxt = p0.next
      # * 两次头向尾
      p0.next.next = cur
      p0.next = pre
      # * 上次头变下次头
      p0 = nxt
    return dummy.next

# * T(n) S(n)
class Solution:
  def lengthOfLongestSubstring(self, s: str) -> int:
    # * 维护一个滑窗
    m = set(); l = 0; ln = 0
    for r, v in enumerate(s):
      # * 在滑窗内，收缩左边
      while v in m: m.remove(s[l]); l += 1
      # * 加入元素
      m.add(v)
      # * 更新最大长度
      ln = max(ln, r - l + 1)
    return ln

# * 从最小覆盖子串的变长滑窗改为定长滑窗
# * 循环某一条件出窗变成固定出窗
# * T(n) S(n)
class Solution:
  def findAnagrams(self, s: str, p: str) -> List[int]:
    res = []; m = defaultdict(int); l = 0; cnt = len(p)
    # * 构建哈希表
    for v in p: m[v] += 1 
    # * 滑窗
    for r, v in enumerate(s):
      # * 满足条件，需求数 - 1
      if m[v] > 0: cnt -= 1
      # * 入窗
      m[v] -= 1
      # * 不满足窗要求
      if r < len(p) - 1: continue
      # * 满足要求，记录结果
      if cnt == 0: res.append(l)
      # * 出窗
      m[s[l]] += 1
      # * 只有要的元素出窗后需求 > 0，补上需求
      if m[s[l]] > 0: cnt += 1
      # * 窗口滑动
      l += 1
    return res

# * T(n) S(n)
# * 前缀和下两个下标值相减可以视作一个子数组
# * 找和为k的子数组可以转化为遍历一个下标
# * 求另一个下标，使得两下标对应值相减为k
# * 也就是两数之和的变种
# * 遍历j，找i s.t. p[j] - p[i] = k
# * => p[i] = p[j] - k是否存在已遍历哈希表中
class Solution:
  def subarraySum(self, nums: List[int], k: int) -> int:
    # * 前缀和
    n = len(nums); p = [0 for _ in range(n + 1)]
    for i, v in enumerate(nums): p[i + 1] = p[i] + v
    # * 和为0的记1个，m[0]就是p[0]的m[v] += 1
    res = 0; m = defaultdict(int); m[0] = 1
    # * 从1开始，因为 j != i (不为空子数组)
    for v in p[1:]:
      if v - k in m: res += m[v - k]
      m[v] += 1
    return res    

# * 单调队列 滑动窗口 + 单调栈 (只修改进入逻辑) 
# * T(n) S(k)
class Solution:
  def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    res = []
    q = deque()
    for i, x in enumerate(nums):
      # * 单调栈进入，外部元素更大时pop队尾
      while q and nums[q[-1]] < x: q.pop()
      q.append(i)
      # * 滑窗超过长度出队头
      if i - q[0] + 1 > k: q.popleft()
      # * 从k-1下标开始滑窗
      if i < k - 1: continue
      res.append(nums[q[0]])
    return res

# * m -> s n -> t
# * T(m + n) S(m)
# * 可以靠复杂度推算法
# * 线性算法: 哈希表 滑动窗口 双指针(链表) 前后缀分解(上升子序列)
class Solution:
  def minWindow(self, s: str, t: str) -> str:
    m = defaultdict(int)
    # * 哈希记录
    for v in t: m[v] += 1
    l = 0; cnt = len(t); ls = 0; ln = 0x3f3f3f3f
    for r, v in enumerate(s):
      # * 符合所需元素，总所需与对应所需减少1
      if m[v] > 0: cnt -= 1
      m[v] -= 1
      # * 当子串满足条件，左边收缩
      while cnt == 0:
        # * 未修改过或有更小结果
        if r - l + 1 < ln: ls = l; ln = r - l + 1
        # * 恢复窗口滑动减少的元素
        m[s[l]] += 1
        # * 如果恢复大于0，需要后续补全所需元素
        if m[s[l]] > 0: cnt += 1
        # * 窗口滑动
        l += 1
    return s[ls: ls + ln] if ln != 0x3f3f3f3f else ''

# * 最大子数组和类DP
# * T(n) S(1)
class Solution:
  def maxSubArray(self, nums: List[int]) -> int:
    # * 两个状态循环数组
    dp = [0, 0]
    # * 子数组最少包含一个元素
    res = nums[0]
    for i, v in enumerate(nums):
      dp[(i + 1) % 2] = max(dp[i % 2] + v, v)
      res = max(res, dp[(i + 1) % 2])
    return res

例
1 2 3 4 5 6 7 k = 3
=> 4 3 2 1 7 6 5 倒数k个与剩余单独反转
=> 5 6 7 1 2 3 4 整体反转
5 6 7 1 2 3 4

# * T(n) S(1)
class Solution:
  def rotate(self, nums: List[int], k: int) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    def reverse(l, r):
      while l < r: 
        nums[l], nums[r] = nums[r], nums[l]
        l += 1; r -= 1
    # * k可能超出n长度
    n = len(nums); k = k % n
    # * 三次反转
    reverse(n - k, n - 1)
    reverse(0, n - k - 1)
    reverse(0, n - 1)

# * 类似接雨水的前后缀分解
# * 通过输出数组避开S(n)
# * T(n) S(1)
class Solution:
  def productExceptSelf(self, nums: List[int]) -> List[int]:
    n = len(nums); res = [1 for _ in range(n)]
    # * 某一点的除自己乘积可以视作
    # * 前缀乘积 * 后缀乘积，也就是一左一右子数组
    # * 一轮算前缀，不算第一个
    pre = 1
    for i in range(1, n):
      # * 前缀累积以上一个
      pre *= nums[i - 1]
      # * 当前位置乘前缀
      res[i] *= pre
    suf = 1
    # * 一轮算后缀，不算最后一个
    for j in range(n - 2, -1, -1):
      suf *= nums[j + 1]
      res[j] *= suf
    return res  

# * T(n) S(1)
class Solution:
  def firstMissingPositive(self, nums: List[int]) -> int:
    # * 结果相当于在三个部分里
    # * 数组左边，那必然是1
    # * 数组中间，找第一个不满足值 = 下标 + 1的位置
    # * 数组右边，对应下标为n，返回 n + 1
    
    # * 数组左边情况：
    # * 找数组里最小的正数
    m = 0x3f3f3f3f
    for v in nums:
      if v > 0 and v < m: m = v
    # * 如果不是1 那结果必然是1
    if m > 1 and m != 0x3f3f3f3f: return 1
    
    # * 数组中间情况：
    # * 最小正数是1 那每个数需要放到自己数值-1的位置
    # * 此条件下，显然大于数组大小的正数不可能
    # * 因为没有其对应位置 负数同理
    # * 处理时认为已经在对应位置
    # * 位置调整
    n = len(nums); i = 0
    while i < n:
      v = nums[i]
      # * 负数和大于n的数(理论位置在数组外)“已经放好” 跳过
      if v <= 0 or v > n: i += 1; continue
      # * 交换nums[i]到该有的位置上
      nums[i], nums[v - 1] = nums[v - 1], nums[i]
      # * 对换回来的nums[i]，如果恰好是正确的位置
      # * （包括正常情况，负数与大于n，两个值相等）
      # * 跳过
      if i == nums[i] - 1 or nums[i] <= 0 or nums[i] > n or nums[i] == nums[v - 1]: i += 1
      # * 否则迭代继续交换位置i
      # * 因为一次至少确定一个位置，所以是T(n)

    # * 最后再次遍历，找出第一个 值对不上下标 + 1的位置
    # * 对应下标 + 1就是结果
    for i, v in enumerate(nums):
      if v - 1 != i: return i + 1
    
    # * 数组右边情况：
    # * 最后如果不存在对不上的，就是缺下标n对应的
    return n + 1

# * T(n) S(1)
class Solution:
  def singleNumber(self, nums: List[int]) -> int:
    # * 纯技巧，0^0=0,0^1=1 => 0的异或不改变值，作数据初值
    res = 0
    # * 偶数个的数异或自己=0（调整顺序计算结果不变）
    # * 最后变为0异或只出现一次的数，得到对应数本身
    for v in nums: res ^= v
    return res
        

# * T(n) S(1)
class Solution:
  def majorityElement(self, nums: List[int]) -> int:
    # * 给每个元素相当于1的血条
    # * 用其他元素去消耗他，当清零时换为下一个，重置为1
    # * 遇到自己就合并血条
    # * 作为多数的元素，在扫描完后：
    # * 它必然能消耗完其他元素
    # * 反过来其他元素总和也不能消耗完这一元素
    cnt = 1; res = nums[0]
    for i in range(1, len(nums)):
      if res == nums[i]: cnt += 1
      else: cnt -= 1
      if cnt == 0: res = nums[i]; cnt = 1 
    return res

# * T(n) S(1)
class Solution:
  def sortColors(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    # * 三路快排的partition
    # * 相当于选取1作为pivot，小于的(0)放左边
    # * 大于的(2)放右边

    # * lt与i交换，lt属于i已经扫过，必然<=，对于交换过来的数据是已知的，i可以+=1
    # * gt与i交换，gt属于i没有扫过，关系位置，对于交换过来的数据是未知的，i不能+=1
    # * 相等时跳过

    # * 三路快排partition模板
    pivot = 1; lt = 0; gt = len(nums) - 1; i = 0
    # * 区间划分[0, lt - 1] [lt, i] [i, gt] [gt + 1, n - 1]
    # * 闭区间写法，可以到gt
    while i <= gt:
      if nums[i] < pivot:
        nums[i], nums[lt] = nums[lt], nums[i]
        lt += 1
        i += 1
      elif nums[i] > pivot:
        nums[i], nums[gt] = nums[gt], nums[i]
        gt -= 1
      else: i += 1

# * T(n) S(1)
class Solution:
  def nextPermutation(self, nums: List[int]) -> None:
    """
    Do not return anything, modify nums in-place instead.
    """
    # * 从 n - 2 开始
    # * 找这样一个位置：
    # * 右边有比她高的数（那么从右开始遍历，这个点会破坏单调递增）
    # * 然后在i右边找到最小的比她大的数
    # * 将她放在位置i上，然后重新i右边从左到右保证单调递增
    # * 这样就能确保为下一个最小排列
    
    # * 当为最大排列循环回去的时候，从右到左必然单调递增
    # * 则找不到i不调整元素顺序
    # * 直接走从左到右确保单增的逻辑，也就是等价于数组反转
    
    
    # * n - 2开始找位置
    n = len(nums); i = n - 2
    # * 寻找破坏从右到左单增的位置
    while i >= 0 and nums[i] >= nums[i + 1]: i -= 1
    # * 右到左单增，找到的第一个大于i的即为
    # * 大于她的最小
    j = n - 1
    # * 如果有这样的位置i
    if i >= 0:
      while nums[j] <= nums[i]: j -= 1
      nums[i], nums[j] = nums[j], nums[i]
    # * 从i+1到n-1保证单增，调换的j有[j - 1] > [j] > [j + 1]
    # * 因为j为最小的大于i的，所以有[j] > [i] > [j + 1]
    # * 于是[j - 1] > [j] > [i] > [j + 1]
    # * i调换后不改变右到左的单增性
    # * 所以只需要反转[i + 1 .. n - 1]即可
    l = i + 1; r = n - 1
    while l < r:
      nums[l], nums[r] = nums[r], nums[l]
      l += 1; r -= 1

# * T(n) S(1)
class Solution:
  def findDuplicate(self, nums: List[int]) -> int:
    # * 当作静态链表，转为找链表的环入口
    # * n + 1个整数，数值范围1 ~ n，访问不会越界
    slow = fast = 0; slow = nums[slow]; fast = nums[nums[fast]]
    # * 将链表分三段
    # * 起点到入口 a 入口到相遇 b 相遇到入口 c
    # * 当快慢相遇有：2(a + b) = a + b + k * (b + c)
    # * 构造得：a - c = (k - 1) * (b + c)
    # * 先令head与slow同走c步 head距离入口a-c，slow走到入口
    # * 此时继续head走a-c步，走到入口，slow同走a-c步=(k-1)*(b+c)即k-1倍环长回到入口
    # * 所以slow与head相遇时即为入口

    # * 流程：快（2倍速度）慢走到相遇
    # * 此时，head与slow同速走到相遇
    # * slow与head即为入口
    while slow != fast:
      slow = nums[slow]; fast = nums[nums[fast]]
    head = 0
    while head != slow:
      slow = nums[slow]; head = nums[head]
    # * nums[slow]表示为next指向的元素
    # * 而初始时已经访问过0的next，所以当下的下标，全部为有效的值
    return slow

# * T(n) S(n)
class Solution:
  def isValid(self, s: str) -> bool:
    st = []
    for c in s:
      # * 左入栈
      if c == '(' or c == '[' or c =='{': st.append(c) 
      # * 右不匹配（对不上或没有东西对）立即返回false
      elif c == ')' and (len(st) == 0 or st[-1] != '('): return False
      elif c == ']' and (len(st) == 0 or st[-1] != '['): return False
      elif c == '}' and (len(st) == 0 or st[-1] != '{'): return False
      # * 右匹配，弹出左
      else: st.pop()
    # * 是否清空栈
    return len(st) == 0

# * T(1) S(push次数)
class MinStack:

  def __init__(self):
    self.st = [(0, inf)]

  def push(self, val: int) -> None:
    # * 记录(当前值，到目前下标为止的最小值)
    self.st.append((val, min(self.st[-1][1], val)))

  def pop(self) -> None:
    self.st.pop()

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

  def getMin(self) -> int:
    return self.st[-1][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()

# * T(n) S(n)
class Solution:
  def decodeString(self, s: str) -> str:
    # * 栈，结果字符串，重复计数
    st = []; res = ''; repeat = 0
    
    for c in s:
      # * 外围的计数与字符串
      # * 外围的字符串是上一次的，用于拼接这一次的
      # * 外围的计数属于这一次，用于构建这一次的字符串
      if c == '[':
        # * 添加本次的计数与上一次的字符串
        st.append((repeat, res))
        # * 清零
        res = ''; repeat = 0
      elif c == ']':
        # * 读取
        cur_repeat, last_res = st.pop()
        # * 上一次字符串（应在数字前）+ 本次计数 * 本次字符串
        res = last_res + cur_repeat * res
      elif '0' <= c <= '9':
        # * 构造数字
        repeat = repeat * 10 + int(c)
      else: 
        # * 构造字符串
        res += c    
    return res