20、有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
class Solution:
def isValid(self, s: str) -> bool:
#定义需要匹配的格式
dic={'(':')','{':'}','[':']'}
stack=['?']
for c in s:
if c in dic:
stack.append(c) #左边压栈
elif dic[stack.pop()] != c: #右边出
return False
return len(stack) == 1
42、接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 感谢 Marcos 贡献此图。
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
# i位置容水量=min(max(i位置左边位置),max(i右边位置)）- i位置的高度
class Solution:
def trap(self, height: List[int]) -> int:
if not height:
return 0
n=len(height)
stack=[]
res=0
for i in range(n):
while stack and height[stack[-1]]<height[i]:
tmp=stack.pop()
if not stack:
break
res+=(min(height[i],height[stack[-1]])-height[tmp])*(i-stack[-1]-1)
stack.append(i)
return res
71、简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
示例 1：
输入："/home/"
输出："/home"
解释：注意，最后一个目录名后面没有斜杠。
示例 2：
输入："/../"
输出："/"
解释：从根目录向上一级是不可行的，因为根是你可以到达的最高级。
示例 3：
输入："/home//foo/"
输出："/home/foo"
解释：在规范路径中，多个连续斜杠需要用一个斜杠替换。
示例 4：
输入："/a/./b/../../c/"
输出："/c"
示例 5：
输入："/a/../../b/../c//.//"
输出："/c"
示例 6：
输入："/a//b////c/d//././/.."
输出："/a/b/c"
# 把当前目录压入栈中,遇到..弹出栈顶,最后返回栈中元素.
class Solution:
def simplifyPath(self, path: str) -> str:
stack = []
path = path.split("/")
for item in path:
if item == "..":
if stack : stack.pop()
elif item and item != ".":
stack.append(item)
return "/" + "/".join(stack)
84、 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
示例:
输入: [2,1,5,6,2,3]
输出: 10
# 最大面积
# i柱子可构造的最大面积=（右边第一个小于i高度的位置-左边第一个小于i高度的位置-1）*i的高度
# 构造单调递增的栈
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack=[]
heights=[0]+heights+[0]
res=0
for i in range(len(heights)):
while stack and heights[stack[-1]]>heights[i]:
tmp=stack.pop()
res=max(res,(i-stack[-1]-1)*heights[tmp])
stack.append(i)
return res
85、最大矩形
给定一个仅包含 0 和 1 的二维二进制矩阵，找出只包含 1 的最大矩形，并返回其面积。
示例:
输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6
#遍历每行的高度，与84题解法类似
class Solution:
def maximalRectangle(self, matrix: List[List[str]]) -> int:
if not matrix or not matrix[0]: return 0
row = len(matrix)
col = len(matrix[0])
height = [0] * (col + 2)
res = 0
for i in range(row):
stack = []
for j in range(col + 2):
if 1<=j<=col:
if matrix[i][j-1] == "1":
height[j] += 1
else:
height[j] = 0
while stack and height[stack[-1]] > height[j]:
cur = stack.pop()
res = max(res, (j - stack[-1] - 1)* height[cur])
stack.append(j)
return res
94、二叉树中序遍历
给定一个二叉树，返回它的中序 遍历。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def inorderTraversal(self, root: TreeNode) -> List[int]:
#二叉树中序遍历 左根右
res=[]
def helper(root):
if not root:
return
helper(root.left)
res.append(root.val)
helper(root.right)
helper(root)
return res
103、 二叉树的锯齿形层次遍历
给定一个二叉树，返回其节点值的锯齿形层次遍历。（即先从左往右，再从右往左进行下一层遍历，以此类推，层与层之间交替进行）。
例如：
给定二叉树 [3,9,20,null,null,15,7],
返回锯齿形层次遍历如下：
[
[3],
[20,9],
[15,7]
]
144、二叉树的前序遍历
给定一个二叉树，返回它的 前序 遍历。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def preorderTraversal(self, root: TreeNode) -> List[int]:
# 前序遍历 根左右
res = []
p = root
stack = []
while p or stack:
while p:
res.append(p.val)
stack.append(p)
p = p.left
p = stack.pop().right
return res
145、二叉树后续遍历
给定一个二叉树，返回它的 后序 遍历。
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution:
def postorderTraversal(self, root: TreeNode) -> List[int]:
# 后续遍历 左右根
"""
:type root: TreeNode
:rtype: List[int]
"""
if root is None:
return []
stack, output = [root, ], []
while stack:
root = stack.pop()
output.append(root.val)
if root.left is not None:
stack.append(root.left)
if root.right is not None:
stack.append(root.right)
return output[::-1]
150、逆波兰表达式求值
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
示例 2：
输入: ["4", "13", "5", "/", "+"]
输出: 6
解释: (4 + (13 / 5)) = 6
示例 3：
输入: ["10", "6", "9", "3", "+", "-11", "", "/", "", "17", "+", "5", "+"]
输出: 22
解释:
((10 * (6 / ((9 + 3) * -11))) + 17) + 5
= ((10 * (6 / (12 * -11))) + 17) + 5
= ((10 * (6 / -132)) + 17) + 5
= ((10 * 0) + 17) + 5
= (0 + 17) + 5
= 17 + 5
= 22
# 遍历序列，数字入栈，到运算符的时候，出栈最后两个数字进行计算，结果入栈
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for t in tokens:
if t in {"+", "-", "/", "*"}:
tmp1 = stack.pop()
tmp2 = stack.pop()
stack.append(str(int(eval(tmp2+t+tmp1))))
else:
stack.append(t)
return stack.pop()
155、最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.
class MinStack:
def __init__(self):
"""
initialize your data structure here.
"""
self.data=[]#数据栈
self.helper=[]#辅助栈
def push(self, x: int) -> None:
self.data.append(x)
if len(self.helper)==0 or x<self.helper[-1]:
self.helper.append(x)
else:
self.helper.append(self.helper[-1])
def pop(self) -> None:
if self.data:
self.helper.pop()
return self.data.pop()
def top(self) -> int:
if self.data:
return self.data[-1]
def getMin(self) -> int:
if self.helper:
return self.helper[-1]
# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()
173、二叉搜索树迭代qi
实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
调用 next() 将返回二叉搜索树中的下一个最小的数。
BSTIterator iterator = new BSTIterator(root);
iterator.next(); // 返回 3
iterator.next(); // 返回 7
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 9
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 15
iterator.hasNext(); // 返回 true
iterator.next(); // 返回 20
iterator.hasNext(); // 返回 false
"""
栈
"""
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class BSTIterator:
def __init__(self, root: TreeNode):
self.stack=[]
self.push_stack(root)
def next(self) -> int:
"""
@return the next smallest number
"""
tmp=self.stack.pop()
if tmp.right:
self.push_stack(tmp.right)
return tmp.val
def hasNext(self) -> bool:
"""
@return whether we have a next smallest number
"""
return bool(self.stack)
def push_stack(self,node):
while node:
self.stack.append(node)
node=node.left
# Your BSTIterator object will be instantiated and called as such:
# obj = BSTIterator(root)
# param_1 = obj.next()
# param_2 = obj.hasNext()
224、基本计算器
实现一个基本的计算器来计算一个简单的字符串表达式的值。
字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格 。
示例 1:
输入: "1 + 1"
输出: 2
示例 2:
输入: " 2-1 + 2 "
输出: 3
示例 3:
输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23
class Solution:
def calculate(self, s: str) -> int:
res = 0
stack = []
sign = 1
i = 0
n = len(s)
while i < n:
if s[i] == " ":
i += 1
elif s[i] == "-":
sign = -1
i += 1
elif s[i] == "+":
sign = 1
i += 1
elif s[i] == "(":
stack.append(res)
stack.append(sign)
res = 0
sign = 1
i += 1
elif s[i] == ")":
# print(stack)
res = res * stack.pop() + stack.pop()
i += 1
elif s[i].isdigit():
tmp = int(s[i])
i += 1
while i < n and s[i].isdigit():
tmp = tmp * 10 + int(s[i])
i += 1
res += tmp * sign
return res
225、用队列实现栈
使用队列实现栈的下列操作：
push(x) -- 元素 x 入栈
pop() -- 移除栈顶元素
top() -- 获取栈顶元素
empty() -- 返回栈是否为空
注意:
你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。
你所使用的语言也许不支持队列。 你可以使用 list 或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。
你可以假设所有操作都是有效的（例如, 对一个空的栈不会调用 pop 或者 top 操作）。
# 队列先进先出
# 栈后进先出
# 队列实现栈-- 两个队列
from queue import Queue
class MyStack:
def __init__(self):
self._queue = Queue()
self._temp = Queue()
def push(self, x: int) -> None:
self._temp.put(x)
while self._queue.qsize() > 0:
self._temp.put(self._queue.get())
while self._temp.qsize() > 0:
self._queue.put(self._temp.get())
def pop(self) -> int:
if self._queue.qsize() > 0:
return self._queue.get()
else:
return None
def top(self) -> int:
if self._queue.qsize() > 0:
x = self._queue.get()
self.push(x)
return x
else:
return None
def empty(self) -> bool:
return self._queue.empty()
# Your MyStack object will be instantiated and called as such:
# obj = MyStack()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.top()
# param_4 = obj.empty()
232、用栈实现队列
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
示例:
MyQueue queue = new MyQueue();
queue.push(1);
queue.push(2);
queue.peek(); // 返回 1
queue.pop(); // 返回 1
queue.empty(); // 返回 false
说明:
你只能使用标准的栈操作 -- 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。
你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端队列）来模拟一个栈，只要是标准的栈操作即可。
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）。
#队列是一种 先进先出（first in - first out， FIFO）的数据结构，队列中的元素都从后端（rear）入队（push），从前端（front）出队（pop）。
#栈是一种 后进先出（last in - first out， LIFO）的数据结构，栈中元素从栈顶（top）压入（push)，也从栈顶弹出（pop）。
#两个栈，一个来反转元素的入队顺序，用另一个来存储元素的最终顺序。
class MyQueue:
def __init__(self):
"""
Initialize your data structure here.
"""
self.A = []
self.B = []
def push(self, x: int) -> None:
"""
Push element x to the back of queue.
"""
self.A.append(x)
def pop(self) -> int:
"""
Removes the element from in front of queue and returns that element.
"""
if self.empty():
return
if len(self.B) == 0:
while len(self.A) != 0:
self.B.append(self.A.pop())
return self.B.pop()
else:
return self.B.pop()
def peek(self) -> int:
"""
Get the front element.
"""
if self.empty():
return
if len(self.B) == 0:
while len(self.A) != 0:
self.B.append(self.A.pop())
return self.B[-1]
else:
return self.B[-1]
def empty(self) -> bool:
"""
Returns whether the queue is empty.
"""
if len(self.B)==0 and len(self.A)==0:
return True
else:
return False
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()
316、去除重复字母
给定一个仅包含小写字母的字符串，去除字符串中重复的字母，使得每个字母只出现一次。需保证返回结果的字典序最小（要求不能打乱其他字符的相对位置）。
示例 1:
输入: "bcabc"
输出: "abc"
示例 2:
输入: "cbacdcbc"
输出: "acdb"
# 字典序是指从前到后比较两个字符串大小的方法。
# 首先比较第 1 个字符，如果不同则第 1 个字符较小的字符串更小；
# 如果相同则继续比较第 2 个字符 …… 如此继续，比较整个字符串的大小。
# ab序列小于ba序列
class Solution:
def removeDuplicateLetters(self, s: str) -> str:
stack=['0']
for i,_ in enumerate(s): # i 是下标，_ 是元素
if _ not in stack:
while _ < stack[-1] and stack[-1] in s[i+1:]:
stack.pop()
stack.append(_)
return ''.join(stack[1:])
331、验证二叉树的前序序列化
序列化二叉树的一种方法是使用前序遍历。当我们遇到一个非空节点时，我们可以记录下这个节点的值。如果它是一个空节点，我们可以使用一个标记值记录，例如 #。
例如，上面的二叉树可以被序列化为字符串 "9,3,4,#,#,1,#,#,2,#,6,#,#"，其中 # 代表一个空节点。
给定一串以逗号分隔的序列，验证它是否是正确的二叉树的前序序列化。编写一个在不重构树的条件下的可行算法。
每个以逗号分隔的字符或为一个整数或为一个表示 null 指针的 '#' 。
你可以认为输入格式总是有效的，例如它永远不会包含两个连续的逗号，比如 "1,,3" 。
示例 1:
输入: "9,3,4,#,#,1,#,#,2,#,6,#,#"
输出: true
示例 2:
输入: "1,#"
输出: false
示例 3:
输入: "9,#,#,1"
输出: false
# 前序遍历根左右
# 用栈模拟前序遍历递归建树的过程
# 如果有两个连续的#，则为空叶子节点，叶子节点的前一个为根节点
class Solution:
def isValidSerialization(self, preorder: str) -> bool:
stack=[]
preorder=preorder.split(",")
for item in preorder:
while stack and stack[-1] == "#" and item == "#":
stack.pop()
if not stack:return False
stack.pop()
stack.append(item)
return len(stack) == 1 and stack[0] == "#"
341、扁平化嵌套列表迭代器
给你一个嵌套的整型列表。请你设计一个迭代器，使其能够遍历这个整型列表中的所有整数。
列表中的每一项或者为一个整数，或者是另一个列表。
示例 1:
输入: [[1,1],2,[1,1]]
输出: [1,1,2,1,1]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,1,2,1,1]。
示例 2:
输入: [1,[4,[6]]]
输出: [1,4,6]
解释: 通过重复调用 next 直到 hasNext 返回 false，next 返回的元素的顺序应该是: [1,4,6]。
# 用栈模拟递归过程
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def isInteger(self) -> bool:
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# """
#
# def getInteger(self) -> int:
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# """
#
# def getList(self) -> [NestedInteger]:
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# """
class NestedIterator:
def __init__(self, nestedList: [NestedInteger]):
self.stack=[]
self.stack.append(nestedList)
self.top=0 #下一个元素
self.flag=False #栈顶元素是否已处理
def next(self) -> int:
self.flag=False #栈顶元素未处理状态
return self.top
def hasNext(self) -> bool:
if len(self.stack)==0:
return False
#栈顶待处理且不为空
while len(self.stack)>0 and not self.flag:
#取出栈顶
top=self.stack.pop()
if isinstance(top,list):
# 如果是列表，取出首元素，并将两者都压入栈
if len(top)>0:
first=top[0]
del top[0]
self.stack.append(top)
self.stack.append(first)
else:
#如果不是列表
if top.isInteger():
#如果是整数，直接取出
self.top=top.getInteger()
self.flag=True
else:
#取出list压入栈
self.stack.append(top.getList())
return self.flag
# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())
385、迷你语法分析器
给定一个用字符串表示的整数的嵌套列表，实现一个解析它的语法分析器。
列表中的每个元素只可能是整数或整数嵌套列表
提示：你可以假定这些字符串都是格式良好的：
字符串非空
字符串不包含空格
字符串只包含数字0-9, [, - ,, ]
示例 1：
给定 s = "324",
你应该返回一个 NestedInteger 对象，其中只包含整数值 324。
示例 2：
给定 s = "[123,[456,[789]]]",
返回一个 NestedInteger 对象包含一个有两个元素的嵌套列表：
- 一个 integer 包含值 123
- 一个包含两个元素的嵌套列表：
i. 一个 integer 包含值 456
ii. 一个包含一个元素的嵌套列表
a. 一个 integer 包含值 789
# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
# def __init__(self, value=None):
# """
# If value is not specified, initializes an empty list.
# Otherwise initializes a single integer equal to value.
# """
#
# def isInteger(self):
# """
# @return True if this NestedInteger holds a single integer, rather than a nested list.
# :rtype bool
# """
#
# def add(self, elem):
# """
# Set this NestedInteger to hold a nested list and adds a nested integer elem to it.
# :rtype void
# """
#
# def setInteger(self, value):
# """
# Set this NestedInteger to hold a single integer equal to value.
# :rtype void
# """
#
# def getInteger(self):
# """
# @return the single integer that this NestedInteger holds, if it holds a single integer
# Return None if this NestedInteger holds a nested list
# :rtype int
# """
#
# def getList(self):
# """
# @return the nested list that this NestedInteger holds, if it holds a nested list
# Return None if this NestedInteger holds a single integer
# :rtype List[NestedInteger]
# """
class Solution:
def deserialize(self, s: str) -> NestedInteger:
if s[0]!='[':
return NestedInteger(int(s))
stack=[]
num,sign,is_num=0,1,False
for c in s:
if c.isdigit():
num=num*10+int(c)
is_num=True
elif c=='-':
sign=-1
elif c=='[':
stack.append(NestedInteger())
elif c==',' or c==']':
#把数字添加进去
if is_num:
cur_list=stack.pop()
cur_list.add(NestedInteger(sign*num))
stack.append(cur_list)
num,sign,is_num=0,1,False
#此时为嵌套列表
if c==']' and len(stack)>1:
cur_list=stack.pop()
stack[-1].add(cur_list)
return stack[0]
394、字符串解码
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例:
s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".
# 栈
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, last_res = stack.pop()
res = last_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res
402、移掉k位数字
给定一个以字符串表示的非负整数 num，移除这个数中的 k 位数字，使得剩下的数字最小。
注意:
num 的长度小于 10002 且 ≥ k。
num 不会包含任何前导零。
示例 1 :
输入: num = "1432219", k = 3
输出: "1219"
解释: 移除掉三个数字 4, 3, 和 2 形成一个新的最小的数字 1219。
示例 2 :
输入: num = "10200", k = 1
输出: "200"
解释: 移掉首位的 1 剩下的数字为 200. 注意输出不能有任何前导零。
示例 3 :
输入: num = "10", k = 2
输出: "0"
解释: 从原数字移除所有的数字，剩余为空就是0。
class Solution:
def removeKdigits(self, num: str, k: int) -> str:
if k>=len(num):
return 0
stack=[]
cnt=k
for n in num:
while stack and stack[-1]>n and k:
stack.pop()
k-=1
stack.append(n)
return str(int("".join(stack[:len(num)-cnt])))
456、132模式
给定一个整数序列：a1, a2, ..., an，一个132模式的子序列 ai, aj, ak 被定义为：当 i < j < k 时，ai < ak < aj。设计一个算法，当给定有 n 个数字的序列时，验证这个序列中是否含有132模式的子序列。
注意：n 的值小于15000。
示例1:
输入: [1, 2, 3, 4]
输出: False
解释: 序列中不存在132模式的子序列。
示例 2:
输入: [3, 1, 4, 2]
输出: True
解释: 序列中有 1 个132模式的子序列： [1, 4, 2].
示例 3:
输入: [-1, 3, 2, 0]
输出: True
解释: 序列中有 3 个132模式的的子序列: [-1, 3, 2], [-1, 3, 0] 和 [-1, 2, 0].
class Solution:
def find132pattern(self, nums: List[int]) -> bool:
le = len(nums)
if le<2: return False
mi = [nums[0]]
for i in range(1, le):
mi.append(min(nums[i], mi[-1]))
stack = []
for i in range(le-1, -1, -1):
print(stack)
if nums[i]>mi[i]:
while stack and mi[i]>=stack[-1]:
stack.pop()
if stack and stack[-1]<nums[i]:
return True
stack.append(nums[i])
return False
496、下一个更大元素I
给定两个没有重复元素的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。
nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出-1。
示例 1:
输入: nums1 = [4,1,2], nums2 = [1,3,4,2].
输出: [-1,3,-1]
解释:
对于num1中的数字4，你无法在第二个数组中找到下一个更大的数字，因此输出 -1。
对于num1中的数字1，第二个数组中数字1右边的下一个较大数字是 3。
对于num1中的数字2，第二个数组中没有下一个更大的数字，因此输出 -1。
示例 2:
输入: nums1 = [2,4], nums2 = [1,2,3,4].
输出: [3,-1]
解释:
对于num1中的数字2，第二个数组中的下一个较大数字是3。
对于num1中的数字4，第二个数组中没有下一个更大的数字，因此输出 -1。
注意:
nums1和nums2中所有元素是唯一的。
nums1和nums2 的数组大小都不超过1000。
# 栈 哈希
class Solution:
def nextGreaterElement(self, nums1: List[int], nums2: List[int]) -> List[int]:
stack, hashmap = list(), dict()
for i in nums2:
while len(stack) != 0 and stack[-1] < i:hashmap[stack.pop()] = i
stack.append(i)
return [hashmap.get(i,-1) for i in nums1]
503、下一个更大元素II
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。
示例 1:
输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。
注意: 输入数组的长度不会超过 10000。
class Solution:
def nextGreaterElements(self, nums: List[int]) -> List[int]:
# 循环数组，使用i%n表示数组索引，不用复制两个一样的数组
# 还是单调栈的思路，其实也是双端队列维护qmax的思想，具体可以参考LeetCode生成窗口最大值数组
n = len(nums)
res = [0 for i in range(n)]
stack = []
# 倒着遍历
for i in range(n*2-1,-1,-1):
while stack and stack[-1] <= nums[i%n]:
stack.pop()
if i < n:
res[i] = stack[-1] if stack else -1
stack.append(nums[i%n])
return res
591、标签验证器
给定一个表示代码片段的字符串，你需要实现一个验证器来解析这段代码，并返回它是否合法。合法的代码片段需要遵守以下的所有规则：
代码必须被合法的闭合标签包围。否则，代码是无效的。
闭合标签（不一定合法）要严格符合格式：<TAG_NAME>TAG_CONTENT</TAG_NAME>。其中，<TAG_NAME>是起始标签，</TAG_NAME>是结束标签。起始和结束标签中的 TAG_NAME 应当相同。当且仅当 TAG_NAME 和 TAG_CONTENT 都是合法的，闭合标签才是合法的。
合法的 TAG_NAME 仅含有大写字母，长度在范围 [1,9] 之间。否则，该 TAG_NAME 是不合法的。
合法的 TAG_CONTENT 可以包含其他合法的闭合标签，cdata （请参考规则7）和任意字符（注意参考规则1）除了不匹配的<、不匹配的起始和结束标签、不匹配的或带有不合法 TAG_NAME 的闭合标签。否则，TAG_CONTENT 是不合法的。
一个起始标签，如果没有具有相同 TAG_NAME 的结束标签与之匹配，是不合法的。反之亦然。不过，你也需要考虑标签嵌套的问题。
一个<，如果你找不到一个后续的>与之匹配，是不合法的。并且当你找到一个<或</时，所有直到下一个>的前的字符，都应当被解析为 TAG_NAME（不一定合法）。
cdata 有如下格式：<![CDATA[CDATA_CONTENT]]>。CDATA_CONTENT 的范围被定义成 <![CDATA[ 和后续的第一个 ]]>之间的字符。
CDATA_CONTENT 可以包含任意字符。cdata 的功能是阻止验证器解析CDATA_CONTENT，所以即使其中有一些字符可以被解析为标签（无论合法还是不合法），也应该将它们视为常规字符。
合法代码的例子:
输入: "<DIV>This is the first line <![CDATA[<div>]]></DIV>"
输出: True
解释:
代码被包含在了闭合的标签内： <DIV> 和 </DIV> 。
TAG_NAME 是合法的，TAG_CONTENT 包含了一些字符和 cdata 。
即使 CDATA_CONTENT 含有不匹配的起始标签和不合法的 TAG_NAME，它应该被视为普通的文本，而不是标签。
所以 TAG_CONTENT 是合法的，因此代码是合法的。最终返回True。
输入: "<DIV>>> ![cdata[]] <![CDATA[<div>]>]]>]]>>]</DIV>"
输出: True
解释:
我们首先将代码分割为： start_tag|tag_content|end_tag 。
start_tag -> "<DIV>"
end_tag -> "</DIV>"
tag_content 也可被分割为： text1|cdata|text2 。
text1 -> ">> ![cdata[]] "
cdata -> "<![CDATA[<div>]>]]>" ，其中 CDATA_CONTENT 为 "<div>]>"
text2 -> "]]>>]"
start_tag 不是 "<DIV>>>" 的原因参照规则 6 。
cdata 不是 "<![CDATA[<div>]>]]>]]>" 的原因参照规则 7 。
不合法代码的例子:
输入: "<A> <B> </A> </B>"
输出: False
解释: 不合法。如果 "<A>" 是闭合的，那么 "<B>" 一定是不匹配的，反之亦然。
输入: "<DIV> div tag is not closed <DIV>"
输出: False
输入: "<DIV> unmatched < </DIV>"
输出: False
输入: "<DIV> closed tags with invalid tag name <b>123</b> </DIV>"
输出: False
输入: "<DIV> unmatched tags with invalid tag name </1234567890> and <CDATA[[]]> </DIV>"
输出: False
输入: "<DIV> unmatched start tag <B> and unmatched end tag </C> </DIV>"
输出: False
注意:
为简明起见，你可以假设输入的代码（包括提到的任意字符）只包含数字, 字母, '<','>','/','!','[',']'和' '。
# ##正则
class Solution:
def isValid(self, code: str) -> bool:
code = re.sub(r'<!\[CDATA\[.*?\]\]>|t', '-', code)
prev = None
while code != prev:
prev = code
code = re.sub(r'<([A-Z]{1,9})>[^<]*</\1>', 't', code)
return code == 't'
636、函数的独占空间
给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。
每个函数都有一个唯一的 Id，从 0 到 n-1，函数可能会递归调用或者被其他函数调用。
日志是具有以下格式的字符串：function_id：start_or_end：timestamp。例如："0:start:0" 表示函数 0 从 0 时刻开始运行。"0:end:0" 表示函数 0 在 0 时刻结束。
函数的独占时间定义是在该方法中花费的时间，调用其他函数花费的时间不算该函数的独占时间。你需要根据函数的 Id 有序地返回每个函数的独占时间。
示例 1:
输入:
n = 2
logs =
["0:start:0",
"1:start:2",
"1:end:5",
"0:end:6"]
输出:[3, 4]
说明：
函数 0 在时刻 0 开始，在执行了 2个时间单位结束于时刻 1。
现在函数 0 调用函数 1，函数 1 在时刻 2 开始，执行 4 个时间单位后结束于时刻 5。
函数 0 再次在时刻 6 开始执行，并在时刻 6 结束运行，从而执行了 1 个时间单位。
所以函数 0 总共的执行了 2 +1 =3 个时间单位，函数 1 总共执行了 4 个时间单位。
说明：
输入的日志会根据时间戳排序，而不是根据日志Id排序。
你的输出会根据函数Id排序，也就意味着你的输出数组中序号为 0 的元素相当于函数 0 的执行时间。
两个函数不会在同时开始或结束。
函数允许被递归调用，直到运行结束。
1 <= n <= 100
#
class Solution:
def exclusiveTime(self, n: int, logs: List[str]) -> List[int]:
res = [0]*n
stack = []
for s in logs:
tmp=s.split(':')
if tmp[1]=='start':
stack.append([int(tmp[0]),int(tmp[2])])
else:
temp = stack.pop()
time = int(tmp[2])-temp[1]+1
res[temp[0]]+=time
if stack:
res[stack[-1][0]]-=time
return res
682、棒球比赛
你现在是棒球比赛记录员。
给定一个字符串列表，每个字符串可以是以下四种类型之一：
1.整数（一轮的得分）：直接表示您在本轮中获得的积分数。
- "+"（一轮的得分）：表示本轮获得的得分是前两轮有效 回合得分的总和。
- "D"（一轮的得分）：表示本轮获得的得分是前一轮有效 回合得分的两倍。
- "C"（一个操作，这不是一个回合的分数）：表示您获得的最后一个有效 回合的分数是无效的，应该被移除。
每一轮的操作都是永久性的，可能会对前一轮和后一轮产生影响。
你需要返回你在所有回合中得分的总和。
示例 1:
输入: ["5","2","C","D","+"]
输出: 30
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到2分。总和是：7。
操作1：第2轮的数据无效。总和是：5。
第3轮：你可以得到10分（第2轮的数据已被删除）。总数是：15。
第4轮：你可以得到5 + 10 = 15分。总数是：30。
示例 2:
输入: ["5","-2","4","C","D","9","+","+"]
输出: 27
解释:
第1轮：你可以得到5分。总和是：5。
第2轮：你可以得到-2分。总数是：3。
第3轮：你可以得到4分。总和是：7。
操作1：第3轮的数据无效。总数是：3。
第4轮：你可以得到-4分（第三轮的数据已被删除）。总和是：-1。
第5轮：你可以得到9分。总数是：8。
第6轮：你可以得到-4 + 9 = 5分。总数是13。
第7轮：你可以得到9 + 5 = 14分。总数是27。
# 栈中只存储有效得分
class Solution:
def calPoints(self, ops: List[str]) -> int:
stack=[]
for i in range(len(ops)):
if ops[i].isdigit():
stack.append(int(ops[i]))
elif ops[i]=="+":
stack.append(stack[-1]+stack[-2])
elif ops[i]=='D':
stack.append(stack[-1]*2)
elif ops[i]=='C':
stack.pop()
return sum(stack)
762、原子的数量
给定一个化学式formula（作为字符串），返回每种原子的数量。
原子总是以一个大写字母开始，接着跟随0个或任意个小写字母，表示原子的名字。
如果数量大于 1，原子后会跟着数字表示原子的数量。如果数量等于 1 则不会跟数字。例如，H2O 和 H2O2 是可行的，但 H1O2 这个表达是不可行的。
两个化学式连在一起是新的化学式。例如 H2O2He3Mg4 也是化学式。
一个括号中的化学式和数字（可选择性添加）也是化学式。例如 (H2O2) 和 (H2O2)3 是化学式。
给定一个化学式，输出所有原子的数量。格式为：第一个（按字典序）原子的名子，跟着它的数量（如果数量大于 1），然后是第二个原子的名字（按字典序），跟着它的数量（如果数量大于 1），以此类推。
示例 1:
输入:
formula = "H2O"
输出: "H2O"
解释:
原子的数量是 {'H': 2, 'O': 1}。
示例 2:
输入:
formula = "Mg(OH)2"
输出: "H2MgO2"
解释:
原子的数量是 {'H': 2, 'Mg': 1, 'O': 2}。
示例 3:
输入:
formula = "K4(ON(SO3)2)2"
输出: "K4N2O14S4"
解释:
原子的数量是 {'K': 4, 'N': 2, 'O': 14, 'S': 4}。
注意:
所有原子的第一个字母为大写，剩余字母都是小写。
formula的长度在[1, 1000]之间。
formula只包含字母、数字和圆括号，并且题目中给定的是合法的化学式。
# 判断大小写
# 判断括号
class Solution:
def countOfAtoms(self, formula: str) -> str:
result_dict = {}
atom_name, tmp_time, cur_time, st = "", "", 1, []
for ch in formula[::-1]:
if ch.isdigit():
tmp_time = ch + tmp_time
elif ch == ")":
if tmp_time == "":
st.append(1)
else:
time = int(tmp_time)
tmp_time = ""
st.append(time)
cur_time *= time
elif ch == "(":
cur_time = cur_time // st.pop()
elif ch.islower():
atom_name = ch + atom_name
else:
atom_name = ch + atom_name
#update(atom_name, tmp_time, cur_time, result_dict)
time = 1 if tmp_time == "" else int(tmp_time)
result_dict[atom_name] = result_dict.setdefault(atom_name, 0) + time * cur_time
atom_name = ""
tmp_time = ""
result = [(atom + ("" if result_dict[atom] == 1 else str(result_dict[atom]))) for atom in sorted(result_dict.keys())]
return "".join(result)
735、行星碰撞✨💥
给定一个整数数组 asteroids，表示在同一行的行星。
对于数组中的每一个元素，其绝对值表示行星的大小，正负表示行星的移动方向（正表示向右移动，负表示向左移动）。每一颗行星以相同的速度移动。
找出碰撞后剩下的所有行星。碰撞规则：两个行星相互碰撞，较小的行星会爆炸。如果两颗行星大小相同，则两颗行星都会爆炸。两颗移动方向相同的行星，永远不会发生碰撞。
示例 1:
输入:
asteroids = [5, 10, -5]
输出: [5, 10]
解释:
10 和 -5 碰撞后只剩下 10。 5 和 10 永远不会发生碰撞。
示例 2:
输入:
asteroids = [8, -8]
输出: []
解释:
8 和 -8 碰撞后，两者都发生爆炸。
示例 3:
输入:
asteroids = [10, 2, -5]
输出: [10]
解释:
2 和 -5 发生碰撞后剩下 -5。10 和 -5 发生碰撞后剩下 10。
示例 4:
输入:
asteroids = [-2, -1, 1, 2]
输出: [-2, -1, 1, 2]
解释:
-2 和 -1 向左移动，而 1 和 2 向右移动。
由于移动方向相同的行星不会发生碰撞，所以最终没有行星发生碰撞。
说明:
数组 asteroids 的长度不超过 10000。
每一颗行星的大小都是非零整数，范围是 [-1000, 1000] 。
# + - 碰撞
class Solution:
def asteroidCollision(self, asteroids: List[int]) -> List[int]:
if len(asteroids)==1:
return asteroids[0]
stack=[-1]
for i in range(len(asteroids)):
if asteroids[i]*stack[-1]<0: #异号
if asteroids[i]+stack[-1]>0:
if abs(stack[-1])<abs(asteroids[i]):
stack.pop()
stack.append(asteroids[i])
elif asteroids[i]+stack[-1]==0:
stack.pop()
elif asteroids[i]*stack[-1]>0: # 同号
stack.append(asteroids[i])
return stack
739、每日温度
根据每日 气温 列表，请重新生成一个列表，对应位置的输入是你需要再等待多久温度才会升高超过该日的天数。如果之后都不会升高，请在该位置用 0 来代替。
例如，给定一个列表 temperatures = [73, 74, 75, 71, 69, 72, 76, 73]，你的输出应该是 [1, 1, 4, 2, 1, 1, 0, 0]。
提示：气温 列表长度的范围是 [1, 30000]。每个气温的值的均为华氏度，都是在 [30, 100] 范围内的整数。
#[73, 74, 75, 71, 69, 72, 76, 73]
# [1, 1, 4, 2, 1, 1, 0, 0]
class Solution:
def dailyTemperatures(self, T: List[int]) -> List[int]:
ans = [0] * len(T)
stack = [] #indexes from hottest to coldest
for i in range(len(T) - 1, -1, -1):
while stack and T[i] >= T[stack[-1]]:
stack.pop()
if stack:
ans[i] = stack[-1] - i
stack.append(i)
return ans
770、基本计算器
给定一个表达式 expression 如 expression = "e + 8 - a + 5" 和一个求值映射，如 {"e": 1}（给定的形式为 evalvars = ["e"] 和 evalints = [1]），返回表示简化表达式的标记列表，例如 ["-1*a","14"]
表达式交替使用块和符号，每个块和符号之间有一个空格。
块要么是括号中的表达式，要么是变量，要么是非负整数。
块是括号中的表达式，变量或非负整数。
变量是一个由小写字母组成的字符串（不包括数字）。请注意，变量可以是多个字母，并注意变量从不具有像 "2x" 或 "-x" 这样的前导系数或一元运算符 。
表达式按通常顺序进行求值：先是括号，然后求乘法，再计算加法和减法。例如，expression = "1 + 2 * 3" 的答案是 ["7"]。
输出格式如下：
对于系数非零的每个自变量项，我们按字典排序的顺序将自变量写在一个项中。例如，我们永远不会写像 “bac” 这样的项，只写 “abc”。
项的次数等于被乘的自变量的数目，并计算重复项。(例如，"aabc" 的次数为 4。)。我们先写出答案的最大次数项，用字典顺序打破关系，此时忽略词的前导系数。
项的前导系数直接放在左边，用星号将它与变量分隔开(如果存在的话)。前导系数 1 仍然要打印出来。
格式良好的一个示例答案是 ["-2aaa", "3aab", "3bb", "4a", "5*c", "-6"] 。
系数为 0 的项（包括常数项）不包括在内。例如，“0” 的表达式输出为 []。
class Solution:
def basicCalculatorIV(self, expression: str, evalvars: List[str], evalints: List[int]) -> List[str]:
class C(collections.Counter):
def __add__(self, other):
self.update(other)
return self
def __sub__(self, other):
self.subtract(other)
return self
def __mul__(self, other):
product = C()
for x in self:
for y in other:
xy = tuple(sorted(x + y))
product[xy] += self[x] * other[y]
return product
vals = dict(zip(evalvars, evalints))
def f(s):
s = str(vals.get(s, s))
return C({(s,): 1}) if s.isalpha() else C({(): int(s)})
c = eval(re.sub('(\w+)', r'f("\1")', expression))
return ['*'.join((str(c[x]),) + x)
for x in sorted(c, key=lambda x: (-len(x), x)) if c[x]]
844、 比较含退格的字符串
给定 S 和 T 两个字符串，当它们分别被输入到空白的文本编辑器后，判断二者是否相等，并返回结果。 # 代表退格字符。
示例 1：
输入：S = "ab#c", T = "ad#c"
输出：true
解释：S 和 T 都会变成 “ac”。
示例 2：
输入：S = "ab##", T = "c#d#"
输出：true
解释：S 和 T 都会变成 “”。
示例 3：
输入：S = "a##c", T = "#a#c"
输出：true
解释：S 和 T 都会变成 “c”。
示例 4：
输入：S = "a#c", T = "b"
输出：false
解释：S 会变成 “c”，但 T 仍然是 “b”。
提示：
1 <= S.length <= 200
1 <= T.length <= 200
S 和 T 只含有小写字母以及字符 '#'。
class Solution:
def backspaceCompare(self, S: str, T: str) -> bool:
s = ""
t = ""
#将输入S翻译成s
for i in S:
if i == "#":
if s:
s = s[:-1]
else:
s = s + i
#将输入T翻译成t
for j in T:
if j == "#":
if t:
t = t[:-1]
else:
t = t + j
return s==t
856、括号的分数
给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
() 得 1 分。
AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分，其中 A 是平衡括号字符串。
示例 1：
输入： "()"
输出： 1
示例 2：
输入： "(())"
输出： 2
示例 3：
输入： "()()"
输出： 2
示例 4：
输入： "(()(()))"
输出： 6
提示：
S 是平衡括号字符串，且只含有 ( 和 ) 。
2 <= S.length <= 50
class Solution:
def scoreOfParentheses(self, S: str) -> int:
num1 = S.replace('()', '+1')
num2 = num1.replace('(', '+2*(')
return eval(num2)
880、索引处的解码字符串
给定一个编码字符串 S。为了找出解码字符串并将其写入磁带，从编码字符串中每次读取一个字符，并采取以下步骤：
如果所读的字符是字母，则将该字母写在磁带上。
如果所读的字符是数字（例如 d），则整个当前磁带总共会被重复写 d-1 次。
现在，对于给定的编码字符串 S 和索引 K，查找并返回解码字符串中的第 K 个字母。
示例 1：
输入：S = "leet2code3", K = 10
输出："o"
解释：
解码后的字符串为 "leetleetcodeleetleetcodeleetleetcode"。
字符串中的第 10 个字母是 "o"。
示例 2：
输入：S = "ha22", K = 5
输出："h"
解释：
解码后的字符串为 "hahahaha"。第 5 个字母是 "h"。
示例 3：
输入：S = "a2345678999999999999999", K = 1
输出："a"
解释：
解码后的字符串为 "a" 重复 8301530446056247680 次。第 1 个字母是 "a"。
提示：
2 <= S.length <= 100
S 只包含小写字母与数字 2 到 9 。
S 以字母开头。
1 <= K <= 10^9
解码后的字符串保证少于 2^63 个字母。
class Solution:
def decodeAtIndex(self, S: str, K: int) -> str:
i = cnt = 0
c = ''
x = []
while i < len(S) and cnt < K:
if S[i].isdigit():
cnt *= int(S[i])
if S[i-1].isdigit(): x[-1][0] = cnt
else: x.append([cnt, len(c) - 1])
else:
c += S[i]
cnt += 1
x.append([cnt, len(c) - 1])
i += 1
ret = ''
while x:
t = x.pop()
K %= t[0]
if K == 0:
ret = c[t[1]]
break
return ret
895、最大频率栈
实现 FreqStack，模拟类似栈的数据结构的操作的一个类。
FreqStack 有两个函数：
push(int x)，将整数 x 推入栈中。
pop()，它移除并返回栈中出现最频繁的元素。
如果最频繁的元素不只一个，则移除并返回最接近栈顶的元素。
示例：
输入：
["FreqStack","push","push","push","push","push","push","pop","pop","pop","pop"],
[[],[5],[7],[5],[7],[4],[5],[],[],[],[]]
输出：[null,null,null,null,null,null,null,5,7,5,4]
解释：
执行六次 .push 操作后，栈自底向上为 [5,7,5,7,4,5]。然后：
pop() -> 返回 5，因为 5 是出现频率最高的。
栈变成 [5,7,5,7,4]。
pop() -> 返回 7，因为 5 和 7 都是频率最高的，但 7 最接近栈顶。
栈变成 [5,7,5,4]。
pop() -> 返回 5 。
栈变成 [5,7,4]。
pop() -> 返回 4 。
栈变成 [5,7]。
提示：
对 FreqStack.push(int x) 的调用中 0 <= x <= 10^9。
如果栈的元素数目为零，则保证不会调用 FreqStack.pop()。
单个测试样例中，对 FreqStack.push 的总调用次数不会超过 10000。
单个测试样例中，对 FreqStack.pop 的总调用次数不会超过 10000。
所有测试样例中，对 FreqStack.push 和 FreqStack.pop 的总调用次数不会超过 150000。
class FreqStack:
def __init__(self):
self.freq = collections.Counter()
self.group = collections.defaultdict(list)
self.maxfreq = 0
def push(self, x):
f = self.freq[x] + 1
self.freq[x] = f
if f > self.maxfreq:
self.maxfreq = f
self.group[f].append(x)
def pop(self):
x = self.group[self.maxfreq].pop()
self.freq[x] -= 1
if not self.group[self.maxfreq]:
self.maxfreq -= 1
return x
# Your FreqStack object will be instantiated and called as such:
# obj = FreqStack()
# obj.push(x)
# param_2 = obj.pop()
896、单调数列
如果数组是单调递增或单调递减的，那么它是单调的。
如果对于所有 i <= j，A[i] <= A[j]，那么数组 A 是单调递增的。 如果对于所有 i <= j，A[i]> = A[j]，那么数组 A 是单调递减的。
当给定的数组 A 是单调数组时返回 true，否则返回 false。
示例 1：
输入：[1,2,2,3]
输出：true
示例 2：
输入：[6,5,4,4]
输出：true
示例 3：
输入：[1,3,2]
输出：false
示例 4：
输入：[1,2,4,5]
输出：true
示例 5：
输入：[1,1,1]
输出：true
提示：
1 <= A.length <= 50000
-100000 <= A[i] <= 100000
class Solution:
def isMonotonic(self, A: List[int]) -> bool:
return (all(A[i] <= A[i+1] for i in range(len(A) - 1)) or
all(A[i] >= A[i+1] for i in range(len(A) - 1)))
"""
class Solution:
def isMonotonic(self, A: List[int]) -> bool:
stack1=[A[0]]
stack2=[A[0]]
for i in range(1,len(A)):
if A[i]>stack1[-1]:
stack1.append(A[i])
elif A[i]<stack1[-1]:
stack2.append(A[i])
else:
stack1.append(A[i])
stack2.append(A[i])
return (len(stack1)==len(A) or len(stack2)==len(A))
"""
901、股票价格跨度
编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。
示例：
输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。
注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。
提示：
调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
每个测试用例最多可以调用 10000 次 StockSpanner.next。
在所有测试用例中，最多调用 150000 次 StockSpanner.next。
此问题的总时间限制减少了 50%。
class StockSpanner:
def __init__(self):
self.stack = []
def next(self, price: int) -> int:
d = 1
while len(self.stack) > 0 and price >= self.stack[-1][0]:
d += self.stack.pop()[1]
self.stack.append((price, d))
return d
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)
907、子数组的最小值之和
给定一个整数数组 A，找到 min(B) 的总和，其中 B 的范围为 A 的每个（连续）子数组。
由于答案可能很大，因此返回答案模 10^9 + 7。
示例：
输入：[3,1,2,4]
输出：17
解释：
子数组为 [3]，[1]，[2]，[4]，[3,1]，[1,2]，[2,4]，[3,1,2]，[1,2,4]，[3,1,2,4]。
最小值为 3，1，2，4，1，1，2，1，1，1，和为 17。
提示：
1 <= A <= 30000
1 <= A[i] <= 30000
class Solution:
def sumSubarrayMins(self, A: List[int]) -> int:
"""
:type A: List[int]
:rtype: int
"""
len_A = len(A)
if len_A == 0:
return 0
if len_A == 1:
return A[0]
ans = 0
left = [0] * len_A
right = [0] * len_A
stack = []
for i in range(len_A):
while stack and A[stack[-1]] > A[i]:
stack.pop()
if not stack:
left[i] = -1
else:
left[i] = stack[-1]
stack.append(i)
stack = []
for i in range(len_A - 1, -1, -1):
while stack and A[stack[-1]] >= A[i]:
stack.pop()
if not stack:
right[i] = len_A
else:
right[i] = stack[-1]
stack.append(i)
for i in range(len_A):
ans += (i - left[i]) * (right[i] - i) * A[i]
ans %= 1000000007
return ans
921、使括号有效的最少添加
给定一个由 '(' 和 ')' 括号组成的字符串 S，我们需要添加最少的括号（ '(' 或是 ')'，可以在任何位置），以使得到的括号字符串有效。
从形式上讲，只有满足下面几点之一，括号字符串才是有效的：
它是一个空字符串，或者
它可以被写成 AB （A 与 B 连接）, 其中 A 和 B 都是有效字符串，或者
它可以被写作 (A)，其中 A 是有效字符串。
给定一个括号字符串，返回为使结果字符串有效而必须添加的最少括号数。
示例 1：
输入："())"
输出：1
示例 2：
输入："((("
输出：3
示例 3：
输入："()"
输出：0
示例 4：
输入："()))(("
输出：4
提示：
S.length <= 1000
S 只包含 '(' 和 ')' 字符。
class Solution:
def minAddToMakeValid(self, S: str) -> int:
stack=[]
for i in range(len(S)):
if (len(stack)==0):
stack.append(S[i])
else:
if S[i]==stack[-1]:
stack.append(S[i])
else:
stack.pop()
return(len(stack))
946、验证栈序列
给定 pushed 和 popped 两个序列，每个序列中的 值都不重复，只有当它们可能是在最初空栈上进行的推入 push 和弹出 pop 操作序列的结果时，返回 true；否则，返回 false 。
示例 1：
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
示例 2：
输入：pushed = [1,2,3,4,5], popped = [4,3,5,1,2]
输出：false
解释：1 不能在 2 之前弹出。
提示：
0 <= pushed.length == popped.length <= 1000
0 <= pushed[i], popped[i] < 1000
pushed 是 popped 的排列。
class Solution:
def validateStackSequences(self, pushed: List[int], popped: List[int]) -> bool:
stack=[pushed[0]]
for i in range(len(pushed)):
if len(stack)>0:
if popped[i]==stack[-1]:
stack.pop()
else:
stack.append(pushed[i])
return (len(stack)==0)
975、奇偶跳
给定一个整数数组 A，你可以从某一起始索引出发，跳跃一定次数。在你跳跃的过程中，第 1、3、5... 次跳跃称为奇数跳跃，而第 2、4、6... 次跳跃称为偶数跳跃。
你可以按以下方式从索引 i 向后跳转到索引 j（其中 i < j）：
在进行奇数跳跃时（如，第 1，3，5... 次跳跃），你将会跳到索引 j，使得 A[i] <= A[j]，A[j] 是可能的最小值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
在进行偶数跳跃时（如，第 2，4，6... 次跳跃），你将会跳到索引 j，使得 A[i] => A[j]，A[j] 是可能的最大值。如果存在多个这样的索引 j，你只能跳到满足要求的最小索引 j 上。
（对于某些索引 i，可能无法进行合乎要求的跳跃。）
如果从某一索引开始跳跃一定次数（可能是 0 次或多次），就可以到达数组的末尾（索引 A.length - 1），那么该索引就会被认为是好的起始索引。
返回好的起始索引的数量。
示例 1：
输入：[10,13,12,14,15]
输出：2
解释：
从起始索引 i = 0 出发，我们可以跳到 i = 2，（因为 A[2] 是 A[1]，A[2]，A[3]，A[4] 中大于或等于 A[0] 的最小值），然后我们就无法继续跳下去了。
从起始索引 i = 1 和 i = 2 出发，我们可以跳到 i = 3，然后我们就无法继续跳下去了。
从起始索引 i = 3 出发，我们可以跳到 i = 4，到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 2 个不同的起始索引（i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
示例 2：
输入：[2,3,1,1,4]
输出：3
解释：
从起始索引 i=0 出发，我们依次可以跳到 i = 1，i = 2，i = 3：
在我们的第一次跳跃（奇数）中，我们先跳到 i = 1，因为 A[1] 是（A[1]，A[2]，A[3]，A[4]）中大于或等于 A[0] 的最小值。
在我们的第二次跳跃（偶数）中，我们从 i = 1 跳到 i = 2，因为 A[2] 是（A[2]，A[3]，A[4]）中小于或等于 A[1] 的最大值。A[3] 也是最大的值，但 2 是一个较小的索引，所以我们只能跳到 i = 2，而不能跳到 i = 3。
在我们的第三次跳跃（奇数）中，我们从 i = 2 跳到 i = 3，因为 A[3] 是（A[3]，A[4]）中大于或等于 A[2] 的最小值。
我们不能从 i = 3 跳到 i = 4，所以起始索引 i = 0 不是好的起始索引。
类似地，我们可以推断：
从起始索引 i = 1 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 2 出发， 我们跳到 i = 3，然后我们就不能再跳了。
从起始索引 i = 3 出发， 我们跳到 i = 4，这样我们就到达数组末尾。
从起始索引 i = 4 出发，我们已经到达数组末尾。
总之，我们可以从 3 个不同的起始索引（i = 1, i = 3, i = 4）出发，通过一定数量的跳跃到达数组末尾。
示例 3：
输入：[5,1,3,4,2]
输出：3
解释：
我们可以从起始索引 1，2，4 出发到达数组末尾。
提示：
1 <= A.length <= 20000
0 <= A[i] < 100000
class Solution:
def oddEvenJumps(self, A: List[int]) -> int:
n = len(A)
def st(data):
s, res = [], [0]*n
for i in data:
while s and s[-1] < i:
res[s.pop()] = i
s.append(i)
return res
d = sorted(range(n), key=lambda i: A[i])
n1, n2 = st(d), st(sorted(d, key=lambda i: -A[i]))
h, l = [0] * n, [0] * n
h[-1] = l[-1] = 1
for i in range(n - 2, -1, -1):
h[i] = l[n1[i]]
l[i] = h[n2[i]]
return sum(h)
1003、检查替换后的词是否有效
给定有效字符串 "abc"。
对于任何有效的字符串 V，我们可以将 V 分成两个部分 X 和 Y，使得 X + Y（X 与 Y 连接）等于 V。（X 或 Y 可以为空。）那么，X + "abc" + Y 也同样是有效的。
例如，如果 S = "abc"，则有效字符串的示例是："abc"，"aabcbc"，"abcabc"，"abcabcababcc"。无效字符串的示例是："abccba"，"ab"，"cababc"，"bac"。
如果给定字符串 S 有效，则返回 true；否则，返回 false。
示例 1：
输入："aabcbc"
输出：true
解释：
从有效字符串 "abc" 开始。
然后我们可以在 "a" 和 "bc" 之间插入另一个 "abc"，产生 "a" + "abc" + "bc"，即 "aabcbc"。
示例 2：
输入："abcabcababcc"
输出：true
解释：
"abcabcabc" 是有效的，它可以视作在原串后连续插入 "abc"。
然后我们可以在最后一个字母之前插入 "abc"，产生 "abcabcab" + "abc" + "c"，即 "abcabcababcc"。
示例 3：
输入："abccba"
输出：false
示例 4：
输入："cababc"
输出：false
提示：
1 <= S.length <= 20000
S[i] 为 'a'、'b'、或 'c'
class Solution:
def isValid(self, S: str) -> bool:
while 'abc' in S:
S = S.replace('abc', '')
return not S
1019、 链表中的下一个更大节点
给出一个以头节点 head 作为第一个节点的链表。链表中的节点分别编号为：node_1, node_2, node_3, ... 。
每个节点都可能有下一个更大值（next larger value）：对于 node_i，如果其 next_larger(node_i) 是 node_j.val，那么就有 j > i 且 node_j.val > node_i.val，而 j 是可能的选项中最小的那个。如果不存在这样的 j，那么下一个更大值为 0 。
返回整数答案数组 answer，其中 answer[i] = next_larger(node_{i+1}) 。
注意：在下面的示例中，诸如 [2,1,5] 这样的输入（不是输出）是链表的序列化表示，其头节点的值为 2，第二个节点值为 1，第三个节点值为 5 。
示例 1：
输入：[2,1,5]
输出：[5,5,0]
示例 2：
输入：[2,7,4,3,5]
输出：[7,0,5,5,0]
示例 3：
输入：[1,7,5,1,9,2,5,1]
输出：[7,9,9,9,0,5,0,0]
提示：
对于链表中的每个节点，1 <= node.val <= 10^9
给定列表的长度在 [0, 10000] 范围内
