用栈一开始就能想到，但是我一开始想的是用两个栈，有一个是用来存放右括号的。
但是你可以一开始push左括号的时候放进去右括号，这样就只要一个栈了。
还有一点是得提前想好有哪几种无效的方式。本题有三种：1.左括号多了；2.右括号多了；3.左右括号对不上。
def isValid(self, s: str) -> bool:
pmap = {'(':')', '{':"}", "[":"]"}
stack = []
for c in s:
if c in pmap:
stack.append(pmap[c])
else:
if len(stack) == 0 or stack.pop() != c:
return False
if len(stack) > 0:
return False
return True
用栈很简单：
def removeDuplicates(self, s: str) -> str:
stack = []
lastInserted = ''
for c in s:
if stack and stack[-1] == c:
stack.pop()
else:
stack.append(c)
return ''.join(stack)
我一开始想：数组删除，why not双指针？后来发现删了之后可能会多出来新的要删的元素，所以失败。
后来发现还是有双指针的方法的：
def removeDuplicates(self, s: str) -> str:
l = list(s)
left, right = 0, 0
while right < len(s):
l[left] = l[right]
if left > 0 and l[left] == l[left-1]:
left -= 1
else:
left += 1
right += 1
return ''.join(l[:left])
注意l[left] = l[right]这个判断要放在最前面，这种比较适合要回看left前面的元素的情况。
ez
def evalRPN(self, tokens: List[str]) -> int:
operators = ["+","-","*","/"]
stack = []
for o in tokens:
if o not in operators:
stack.append(o)
else:
right = stack.pop()
left = stack.pop()
stack.append(str(int(eval(left+o+right))))
return int(stack[0])
先手撸一个模拟，虽然有优化可以应对大部分情况，但是某些情况下如果一直走到res.append(max(d))里面就是O(kn)的复杂度，超时。
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
right = k-1
d = deque(nums[:right])
lastrmved = 0
while right < len(nums):
d.append(nums[right])
if len(res) == 0 or lastrmved == res[-1]:
res.append(max(d))
else:
res.append(max(nums[right], res[-1]))
lastrmved = d.popleft()
right += 1
return res
这时应该发现现成数据结构的问题了：deque可以支持模拟滑动窗口，但是要找窗口内的最大值还得O(k)遍历；heapq可以直接找到窗口内的最大值，但是不能删除移出滑动窗口的元素。
所以想定义一个自己的数据结构Q，支持以下操作：
push: 向Q的尾部增加一个元素。
pop: 从Q的头部弹出一个元素。
(这两个操作和普通的queue没有区别)
max：获得Q中元素的最大值。该操作的时间需要控制在O(1). 实现该方法时的最大问题：pop掉了max之后，下一个max应该怎么找到？
注：这种数据结构又叫单调链表。目前除了这题我想不出单调链表还能用在哪（流汗黄豆）。
首先来一个O(nlogn)的普通解法（但是不知道为什么时间已经超越了99%的用户）。主要是想秀一下python API。
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freqs = Counter(nums)
res = []
items = list(freqs.items())
items.sort(reverse=True, key=lambda t:t[1])
return list(map(lambda x:x[0], items[:k]))
挑战是使用优于nlogn的复杂度完成本题。略加思考，可以使用大小为k的堆将复杂度降到nlogk：
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freqs = Counter(nums)
res = []
l = list(map(lambda t:(t[1], t[0]), list(freqs.items())))
heap = []
for t in l:
heapq.heappush(heap, t)
if len(heap) > k:
heapq.heappop(heap)
return list(map(lambda t:t[1], heap))
彳亍。注意python的堆是支持有优先级的tuple的，但是优先级要放在tuple的第一个元素。
栈，队列，堆。这些东西好好上过61b的应该随便干吧。
栈在解决配对问题时非常有用。
学习了一个新的数据结构：单调队列。