文章目录
栈和队列以及优先队列
1.栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）
思路：
- 将 pushed 队列中的每个数都 push 到栈中，同时检查这个数是不是 popped 序列中下一个要 pop 的值，如果是就把它 pop 出来。
最后，检查不是所有的该 pop 出来的值都是 pop 出来了。时间复杂度O(n)，空间复杂度O(n)
class Solution {
public:
bool validateStackSequences(vector<int>& pushV, vector<int>& popV) {
if (pushV.empty() || popV.empty() || pushV.size() != popV.size())
return true;
std::stack<int> QQ;
int index = 0;
// 遍历的是 push 序列
for (const auto &it : pushV)
{
QQ.push(it);
//栈不空 数组下标不越界 （如果不相等就继续把 push 序列的数字压入栈中）
while (!QQ.empty() && index < pushV.size() && QQ.top() == popV[index])
{
QQ.pop();
index++;
}
}
return index == pushV.size();
}
};
2. 返回滑动窗口中的最大值
https://leetcode-cn.com/problems/sliding-window-maximum/
解法一：
使用优先队列，维护一个k个元素的 大顶堆（Java中是使用一个完全二叉树实现）。
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0 || nums.length <= 0) {
return null;
}
// 创建一个大顶堆，需要自定义比较器
PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>(k, new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < k; i++) {
priorityQueue.add(nums[i]);
}
int[] result = new int[nums.length - k + 1];
result[0] = priorityQueue.peek();
// 每轮要移除的元素(滑动窗口最左边的一个元素,注意是 nums[0],而不是 队列首元素)
int last = nums[0];
for (int i = k; i < nums.length; i++) {
// 移除滑动窗口之外的元素
priorityQueue.remove(last);
// 添加新元素
priorityQueue.add(nums[i]);
// 取优先队列的最大首元素
result[i - k + 1] = priorityQueue.peek();
// 记录每轮要移除的元素（滑动窗口最左边的元素）
last = nums[i - k + 1];
}
return result;
}
}
- 时间复杂度：O(nlogn)，其中 nn 是数组 \textit{nums}nums 的长度。在最坏情况下，数组 \textit{nums}nums 中的元素单调递增，那么最终优先队列中包含了所有元素，没有元素被移除。由于将一个元素放入优先队列的时间复杂度为 O(\log n)O(logn)，因此总时间复杂度为 O(n \log n)O(nlogn)。
- 空间复杂度：O(n)O(n)，即为优先队列需要使用的空间。这里所有的空间复杂度分析都不考虑返回的答案需要的 O(n)O(n) 空间，只计算额外的空间使用。
解法二：
使用一个双端队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || k <= 0 || nums.length <= 0) {
return null;
}
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; i++) {
// 双向队列 保存当前窗口最大值的数组位置 保证队列中数组位置的数值按从大到小排序
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
//数组下标：放到双端队列最后
deque.offerLast(i);
}
int[] result = new int[nums.length - k + 1];
// 取队列的最大首元素
result[0] = nums[deque.peekFirst()];
for (int i = k; i < nums.length; i++) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}
}
-
时间复杂度：O(n)O(n)，其中 nn 是数组 \textit{nums}nums 的长度。每一个下标恰好被放入队列一次，并且最多被弹出队列一次，因此时间复杂度为 O(n)O(n)。
-
空间复杂度：O(k)O(k)。与方法一不同的是，在方法二中我们使用的数据结构是双向的，因此「不断从队首弹出元素」保证了队列中最多不会有超过 k+1k+1 个元素，因此队列使用的空间为 O(k)O(k)。
3. 返回数据流中的第K大元素
思路：
class KthLargest {
PriorityQueue<Integer> pq;
final int k;
public KthLargest(int k, int[] nums) {
this.k = k;
pq = new PriorityQueue<Integer>();
for (int x : nums) {
add(x);
}
}
public int add(int val) {
//如果还不是一个K的最小堆的话，就先添加上去，直接返回堆顶
if (pq.size() < k) {
pq.add(val);
}
// 现在绝对是一个K的最小堆，那么按照逻辑判断即可
else if(val > pq.peek()){
pq.poll();
pq.add(val);
}
return pq.peek();
}
}
- 时间复杂度：O(n*log(k))
- 空间复杂度：O(k)