重要知识
1. Java stack
- pop 拉出，push 压入栈顶，peek 看一眼栈顶（不改变元素），search查找（不改变元素，时间复杂度为n）
2. java queue
- 直接在谷歌搜索 queue Java
- add 和 remove会抛出异常，offer 和 poll 会返回特定值
3. deque （双端队列）
-
Java操作见图即可
4. priority queue（优先队列）
- 插入复杂度为 1，取出复杂度为log n
- 底层实现的数据结构多样和复杂，用的是heap（堆），but 不一定够是二叉堆，也有可能是斐波那契堆，平衡二叉树（红黑树eg）
5. 总结
刷题技巧
- 如果一个题目具有最近相关性的话就可以考虑用 stack 来解决（剥洋葱），讲究先来后到用queue
- 栈和队列相关问题很多可以用双栈or双队列来解决
- i,j枚举，两边扩散，中间聚拢的代码一定要写的滚瓜烂熟！！！
- 优化代码主要是考虑前面的步骤是否有重复的，可以记录的
- 所有滑动窗口的题目基本都是用双端队列解决
网友评论