文章目录

• 栈和队列以及优先队列
• • • 1.栈的压入、弹出序列
  • 2. 返回滑动窗口中的最大值
  • • 解法一：
    • 解法二：
    • 3. 返回数据流中的第K大元素

栈和队列以及优先队列

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大元素

703. 数据流中的第 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)