Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit86b06c1

Browse files
edit 239
1 parentaa6a4f6 commit86b06c1

File tree

2 files changed

+19
-28
lines changed

2 files changed

+19
-28
lines changed

‎src/main/java/com/fishercoder/solutions/_239.java

Lines changed: 16 additions & 25 deletions
Original file line numberDiff line numberDiff line change
@@ -3,6 +3,8 @@
33
importjava.util.*;
44

55
/**
6+
* 239. Sliding Window Maximum
7+
*
68
* Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right.
79
* You can only see the k numbers in the window. Each time the sliding window moves right by one position.
810
@@ -11,7 +13,7 @@
1113
1214
Window position Max
1315
--------------- -----
14-
[1 3 -1] -3 5 3 6 73
16+
[1 3 -1] -3 5 3 6 7 3
1517
1 [3 -1 -3] 5 3 6 7 3
1618
1 3 [-1 -3 5] 3 6 7 5
1719
1 3 -1 [-3 5 3] 6 7 5
@@ -34,32 +36,21 @@ How about using a data structure such as deque (double-ended queue)?
3436
publicclass_239 {
3537

3638
publicint[]maxSlidingWindow(int[]nums,intk) {
37-
if(nums ==null ||nums.length ==0 ||k ==0)returnnewint[0];
38-
Queue<Integer>heap =newPriorityQueue<Integer>(newComparator<Integer>(){
39-
@Override
40-
publicintcompare(Integero1,Integero2) {
41-
if(o1 >o2)return -1;
42-
elseif(o1 <o2)return1;
43-
elsereturn0;
39+
if (nums ==null ||nums.length ==0 ||k ==0)returnnewint[0];
40+
PriorityQueue<Integer>heap =newPriorityQueue<>((a,b) ->b -a);
41+
int[]res =newint[nums.length -k +1];
42+
for (inti =0;i <nums.length;i++) {
43+
if (i <k) {
44+
heap.offer(nums[i]);
45+
if (i ==k -1) {
46+
res[0] =heap.peek();
47+
}
48+
}else {
49+
heap.remove(nums[i -k]);
50+
heap.offer(nums[i]);
51+
res[i -k +1] =heap.peek();
4452
}
4553
}
46-
);
47-
inti =0;
48-
for(;i <k;i++){
49-
heap.offer(nums[i]);
50-
}
51-
List<Integer>list =newArrayList<Integer>();
52-
list.add(heap.peek());
53-
for(;i <nums.length;i++){
54-
heap.remove(nums[i-k]);
55-
heap.offer(nums[i]);
56-
list.add(heap.peek());
57-
}
58-
int[]res =newint[list.size()];
59-
for(intj =0;j <list.size();j++){
60-
res[j] =list.get(j);
61-
}
6254
returnres;
6355
}
64-
6556
}

‎src/test/java/com/fishercoder/_239Test.java

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -23,9 +23,9 @@ public static void setup(){
2323

2424
@Before
2525
publicvoidsetupForEachTest(){
26-
expected =newint[1000];
27-
actual =newint[1000];
28-
nums =newint[1000];
26+
expected =newint[]{};
27+
actual =newint[]{};
28+
nums =newint[]{};
2929
k =0;
3030
}
3131

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp