题目： 61. 二叉搜索树的第k个结点，62. 数据流中的中位数，63. 滑动窗口的最大值
61. 二叉搜索树的第k个结点
给定一颗二叉搜索树，请找出其中的第k大的结点（此处题目表达有些不准确，应该为第k小结点）。例如， 5 / \ 3 7 /\ /\ 2 4 6 8 中，按结点数值大小顺序第三个结点的值为4。
思路：二叉搜索树的中序遍历是排好序的，因此中序遍历输出第k个结点即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
import java.util.Stack;
/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;
public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
TreeNode KthNode(TreeNode pRoot, int k){
if(pRoot == null || k == 0) return null;
Stack<TreeNode> stack = new Stack<TreeNode>();
TreeNode node = pRoot;
int count = 0;
do{
if(node != null){
stack.push(node);
node = node.left;
}
else{
node = stack.pop();
count++;
if(count == k) return node;
node = node.right;
}
} while(!stack.isEmpty() || node!=null);
return null;
}
}
62. 数据流中的中位数
如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。
思路： 用一个最大堆和一个最小堆将数据流分成两部分，最大堆中的所有元素需要小于最小堆，两个堆的元素数量之差需要小于1，满足这两个条件之后，当元素总数为偶数时，两个堆定元素的平均数就是中位数；当元素总数是奇数时，元素数量多的堆的堆顶就是中位数。因此可以采用一种策略，用一个计数器，当放入的元素是第奇数个的时候，先将元素放入最大堆，调整完结构将最大堆顶放入最小堆；放入元素是偶数个的时候，先将元素放进最小堆，再取除最小堆的堆顶放入最大堆。这样就能确保两个堆的数量相等或差不超过1，且小堆元素总是大于大堆元素。
这里用到的容器是PriorityQueue，默认最小堆，最大堆需要重写compare方法。PriorityQueue具体可以看这篇文章：Java堆结构PriorityQueue完全解析。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.PriorityQueue;
import java.util.Comparator;
public class Solution {
private PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>();
private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>(){
@Override
public int compare(Integer o1, Integer o2){
return o2.compareTo(o1);
}
});
private static int count = 0;
public void Insert(Integer num) {
count++;
if((count & 1) == 1){
maxHeap.offer(num);
minHeap.offer(maxHeap.poll());
}
else{
minHeap.offer(num);
maxHeap.offer(minHeap.poll());
}
}
public Double GetMedian() {
if(count == 0) {
throw new RuntimeException("No numbers in stream!");
}
if((count & 1) == 0) return (double)(minHeap.peek() + maxHeap.peek())/2;
else return (double)minHeap.peek();
}
}
63. 滑动窗口的最大值
给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。
思路： 用一个双端队列存取数组下标di，当第i个元素进入队列，若尾部num[di]比num[i]小，弹出di，当队列头部元素与i的差值大于等于size时，说明头部元素已经不在窗口中，弹出头部元素。做完上述处理之后，将i存入队列。当i大于等于size - 1开始，将队头num[di]存入结果。
例，
数组[2, 3, 4, 2, 6, 2, 5, 1]，窗口大小size = 3。
iteration1:
队列[0]，进入元素num[1] = 3，num[1] > num[0]，弹出队列尾部元素；
队列空，不判断；
队列加入1
iteration2:
队列[1]，进入元素num[2] = 4，num[2] > num[1]，弹出队列尾部元素；
队列空，不判断；
队列加入2；
2 >= size - 1，将队头元素对应的数组数字存入结果。res=[4]
iteration3:
队列[2]，进入元素num[3] = 2，num[3] < num[2]，无需操作队列；
队头元素2，此时3 - 2 < size，说明队头还在窗口内；
队列加入3；
3 >= size - 1，将队头元素对应的数组数字存入结果。res=[4，4]
iteration4:
队列[2，3]，进入元素num[4] = 6，num[4] > num[3]，弹出队列尾部元素；
num[4] > num[2]，继续弹出队列尾部元素；
队头元素4，此时4 - 2 < size，说明队头还在窗口内；
队列加入4；
4 >= size - 1，将队头元素对应的数组数字存入结果。res=[4，4，6]
….
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int [] num, int size){
LinkedList<Integer> deque = new LinkedList<Integer>();
ArrayList<Integer> res = new ArrayList<Integer>();
if(num.length == 0 || size == 0) return res;
for(int i = 0; i < num.length; i++){
while(deque.size() > 0 && num[deque.getLast()] < num[i]) deque.removeLast();
if(deque.size() > 0 && i - deque.getFirst() >= size) deque.removeFirst();
deque.add(i);
if(i >= size - 1) res.add(num[deque.getFirst()]);
}
return res;
}
}