第三天(栈)

---

创建时间： 2020/7/21 12:09

---

今天完成题目：496，225，232，1441，1629，1565，155，844，20

496：下一个更大元素

• 在python3.x中判断字典中有无key要用dict.__contains__(key)

• 此题记得思路转换为求nums2中的递减栈，当遇到较大值时，则将比它小的pop出来并添加到字典中作为结果

225：用队列实现栈

• 我采用的是list的方式，但是时间和空间上效果显示不好

• 还有以下两种方式可以倒入队列或双队列

  • from queue import Queue

  • from collections import deque\

232：用栈实现队列（跟第二天的双栈实现队列一样）

1441：用栈操作数组

• list.pop(0)可以弹出第一个数\

1629：栈的最小值（O（1）复杂度实现）

• 建立两个栈，一个是正常模拟栈操作，一个是递减栈，当栈的值小于等于栈顶的时候才能入

• 之所以是小于等于，是因为有重复的最小元素

• 递减栈相当于保留正常栈按顺序从大到小的一个列表。没有保存到的值大小在两个递减栈元素之间，被pop也不会对最小值产生影响

1565：包含min的栈（跟1629一致）

155：最小栈（跟1629一致）

• 官方提供了一种方法，默认递减栈首元素为math.inf即无穷大值

• 使用self.min_stack.append(min(x, self.min_stack[-1]))来为递减栈push，从而不需要判断，pop时候也能直接pop栈顶

844：比较含退格的字符串

• 用字符串当栈来比较

• 用list当栈来比较，pop操作比字符串的截取速度更快\

20：有效的括号

• 左括号等于进栈，右括号等于出栈

• 需要考虑细节，例如输入空""，出栈时为空“}”等

• 所以，仅从正确的输入方式出发，当发现不符合时，直接返回False

�