队列与栈相关题目
2018-12-27 本文已影响0人
pokorz
- 使用栈模拟队列操作
- 题目链接: https://leetcode.com/problems/implement-queue-using-stacks/
- 解题思路
使用两个栈一个用来做输入，一个用来做输出
- 使用队列模拟栈操作
- 题目链接
https://leetcode.com/problems/implement-stack-using-queues/ - 解题思路
同样也是使用两个队列模拟，不同点在于第一个队列要空的最后一个元素作为出栈元素
- 题目链接
- 寻找第k大元素
高频面试题，求解数组中第k大的元素- 题目链接
https://leetcode.com/problems/kth-largest-element-in-a-stream/ - 解题思路
维护一个小顶堆，即从小到大的优先队列，先填满，然后遇到比堆顶元素大的放入堆中，并把堆顶元素挤出反之则忽略。
代码见github
- 题目链接
- 滑动窗口中求解最大值
- 给定一个数组，与一个k值，求解k个大的区间内的最大值
https://leetcode.com/problems/sliding-window-maximum/ - 解题思路
可以使用大小为k的优先队列，这是思路1
还有一种方法是使用双端队列，每次入队的时候比较下之前的元素，如果都比前面的大，那把比之大的都出队，然后将其入队，这样可以做到，每次队首元素都是最大值。这里要注意的是双端队列中需要保存给定数组的索引，来保证队首元素的区间在k滑动窗口内，具体代码见github
- 给定一个数组，与一个k值，求解k个大的区间内的最大值
