用两个栈实现队列
用两个栈来实现一个队列，完成队列的 Push 和 Pop 操作。
- 栈先入后出，队列先进先出。
所以入栈一次出一次，序列相反。再入栈一次出栈一次，成序列相同。
第一次：入1-2-3 出3-2-1
第二次：入3-2-1 出1-2-3
Stack<Integer> in = new Stack<Integer>();
out.isEmpty()
in.push(node);
out.push(in.pop());
包含 min 函数的栈
实现一个包含 min() 函数的栈，该方法返回当前栈中最小的值。
- 2个栈，一个直接放数据。一个进行比较，将较小的数据放入第二个栈中去。
minStack.push(minStack.isEmpty() ? node : Math.min(minStack.peek(), node));
//感觉像固定写法
public void pop() {
dataStack.pop();
minStack.pop();
}
栈的压入、弹出序列
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否为该栈的弹出顺序。假设压入栈的所有数字均不相等。
- 入栈的时候比较一下是不是出栈序列的当前值，是的话，出了，不是的话，继续加。到最后看有没有出完即可。
return stack.isEmpty();
最小的 K 个数
给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。
要求：空间复杂度 O(n)O(n) ，时间复杂度 O(nlogn)O(nlogn)
- 大小为k的最小堆
- 构建一个大顶堆，取大顶堆前几位。
- 初始化实现大顶堆，不设置则默认为小顶堆。
- PriorityQueue<Integer> maxHeap = new PriorityQueue<>
((o1, o2) -> o2 - o1); - 输出第一个数，并删除。
maxHeap.poll();
返回堆的队列
return new ArrayList<>(maxHeap);
- 快排
- 快速排序的方法，找到第K的数的位置。
- 每执行一次快排，某个数之前一定是小于它的，之后一定是大于它的。
数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
- 大小顶堆
- 数据流是一个串，假设排序完成，我将它分为2部分。
- 这样最半部分取最大值，右半部分取最小值，实现其平均数的结果。
- 当N为偶数，右半边的数要全大于左边，所以先往左插，再插右。基数相反。
left.add(val);
right.add(left.poll());
字符流中第一个不重复的字符2022.7.9-3
请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符 "go" 时，第一个只出现一次的字符是 "g"。当从该字符流中读出前六个字符“google" 时，第一个只出现一次的字符是 "l"。
- 队列，我的第一个数字，一定是只出现一次的，且一定是第一次出现的。之后出现了第二次，就把它出了。
private int[] cnts = new int[128];
private Queue<Character> queue = new LinkedList<>();
public void Insert(char ch) {
cnts[ch]++;
queue.add(ch);
while (!queue.isEmpty() && cnts[queue.peek()] > 1)
queue.poll();
}
public char FirstAppearingOnce() {
return queue.isEmpty() ? '#' : queue.peek();
}
滑动窗口的最大值2022.7.9-4
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。
例如，如果输入数组 {2, 3, 4, 2, 6, 2, 5, 1} 及滑动窗口的大小 3，那么一共存在 6 个滑动窗口，他们的最大值分别为 {4, 4, 6, 6, 6, 5}。
- 堆的维护，直接生成一个结果堆，然后对它进行维护。
可以直接删除某个数
heap.remove(num[i]);
heap.add(num[j]);
ret.add(heap.peek());
