题目描述
给定一个包含 n 个整数的数组，和一个大小为 k 的滑动窗口,从左到右在数组中滑动这个窗口，找到数组中每个窗口内的最大值
样例
对于数组 [1,2,7,8,5], 滑动大小 k = 3 的窗口时，返回 [2,7,7]
最初，窗口的数组是这样的：
[ | 1,2,7 | ,8,5] , 返回中位数 2;
接着，窗口继续向前滑动一次。
[1, | 2,7,8 | ,5], 返回中位数 7;
接着，窗口继续向前滑动一次。
[1,2, | 7,8,5 | ], 返回中位数 7;
思路
1、构造一个大顶堆一个小顶堆
2、对前k个元素，将小于num[0]的元素放入大顶堆，大于num[0]的元素放入小顶堆
3、平衡小顶堆和大顶堆元素的数目后，得到中位数
4、从堆中删除nums[0]
5、每次根据后一个元素大小决定其放入的堆，平衡两个堆的数目后，得到中位数
6、删除旧元素后，回到第五步，直到访问完所有元素
堆中增加元素lgn复杂度，遍历数组的复杂度为n，所以时间复杂度：nlgn
代码
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
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
| public class Solution {
public class minComparator implements Comparator<Integer> {
public int compare(Integer a, Integer b){
if(a > b) return 1;
else if(a == b) return 0;
else return -1;
}
}
public class maxComparator implements Comparator<Integer> {
public int compare(Integer a, Integer b){
if(a > b) return -1;
else if(a == b) return 0;
else return 1;
}
}
/**
* @param nums: A list of integers.
* @return: The median of the element inside the window at each moving.
*/
public ArrayList<Integer> medianSlidingWindow(int[] nums, int k) {
// write your code here
ArrayList<Integer> res = new ArrayList<>();
// exception
if(k == 1) {
Integer[] ints = new Integer[nums.length];
for(int i = 0; i < nums.length; i++) {
ints[i] = nums[i];
}
return new ArrayList<Integer>(Arrays.asList(ints));
}
if(k == 2) {
for(int i = 0; i < nums.length-1; i++) {
res.add(Math.min(nums[i], nums[i+1]));
}
return res;
}
// init heap
PriorityQueue<Integer> MaxHeap = new PriorityQueue<>(new maxComparator());
PriorityQueue<Integer> MinHeap = new PriorityQueue<>(new minComparator());
MaxHeap.add(nums[0]);
for(int i = 1; i < k; i++) {
if(nums[i] > nums[0]) {
MinHeap.add(nums[i]);
}else {
MaxHeap.add(nums[i]);
}
}
if(k % 2 == 1) {
if(MinHeap.size() > MaxHeap.size()) {
while(( MinHeap.size()-MaxHeap.size() ) != 1) {
MaxHeap.add(MinHeap.poll());
}
res.add(MinHeap.peek());
// 删除旧元素，并使得小堆和大堆平衡
MaxHeap.add(MinHeap.poll());
MaxHeap.remove(nums[0]);
}else {
while( ( MaxHeap.size()-MinHeap.size() ) != 1 ) {
MinHeap.add(MaxHeap.poll());
}
res.add(MaxHeap.peek());
// 删除旧元素，并使得小堆和大堆平衡
MinHeap.add(MaxHeap.poll());
MinHeap.remove(nums[0]);
}
}else {
if(MaxHeap.size() > MinHeap.size()) {
while(MaxHeap.size() != MinHeap.size()) {
MinHeap.add(MaxHeap.poll());
}
res.add(MaxHeap.peek());
MinHeap.remove(nums[0]);
}else if(MaxHeap.size() < MinHeap.size()) {
while( MaxHeap.size() != MinHeap.size() ){
MaxHeap.add(MinHeap.poll());
}
res.add(MaxHeap.peek());
MaxHeap.remove(nums[0]);
}else {
res.add(MaxHeap.peek());
MaxHeap.remove(nums[0]);
}
}
// 寻找第k个数字之后的中位数
for(int i = k; i < nums.length; i++) {
// 新数入堆
if(nums[i] > MinHeap.peek()) {
MinHeap.add(nums[i]);
}else {
MaxHeap.add(nums[i]);
}
// 分K为偶数奇数找到中位数
if(k % 2 == 1) {
if(MinHeap.size() > MaxHeap.size()) {
// 使大小堆数目平衡
while(( MinHeap.size()-MaxHeap.size() ) != 1) {
MaxHeap.add(MinHeap.poll());
}
// 找到中位数
res.add(MinHeap.peek());
}else {
// 使大小堆数目平衡
while( ( MaxHeap.size()-MinHeap.size() ) != 1 ) {
MinHeap.add(MaxHeap.poll());
}
// 找到中位数
res.add(MaxHeap.peek());
}
}else {
if(MaxHeap.size() > MinHeap.size()) {
// 使大小堆数目平衡
while(MaxHeap.size() != MinHeap.size()) {
MinHeap.add(MaxHeap.poll());
}
// 找到中位数
res.add(MaxHeap.peek());
}else if(MaxHeap.size() < MinHeap.size()) {
// 使大小堆数目平衡
while( MaxHeap.size() != MinHeap.size() ){
MaxHeap.add(MinHeap.poll());
}
// 找到中位数
res.add(MaxHeap.peek());
}else {
// 找到中位数
res.add(MaxHeap.peek());
}
}
// 丢掉最左边的数
if(nums[i-k+1] >= MinHeap.peek()) {
MinHeap.remove(nums[i-k+1]);
}else {
MaxHeap.remove(nums[i-k+1]);
}
}
return res;
}
public static void main(String args[]) {
Solution solution = new Solution();
ArrayList<Integer> list = solution.medianSlidingWindow(new int[]{1,2,3,5,3,5,1,2,7,4,3,9,6}, 1);
for(int num : list) {
System.out.print(num);
}
}
}
|
考差点