-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathProblem239.java
More file actions
116 lines (99 loc) · 3 KB
/
Problem239.java
File metadata and controls
116 lines (99 loc) · 3 KB
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
package com.leetcode.problems;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
class Solution239 {
/**
* 方法1 结果是 使用优先队列 超时
* @param nums
* @param k
* @return
*/
public int[] maxSlidingWindow(int[] nums, int k) {
class priQueue{
private LinkedList<Integer> q = new LinkedList<>();
public void push(int n){
while (!q.isEmpty()&&q.getLast()<n)
{
q.removeLast();
}
q.addLast(n);
}
public int max(){
return q.getFirst();
}
public void pop(int n){
if(n==q.getFirst())
{
q.removeFirst();
}
}
}
ArrayList<Integer> res = new ArrayList<>();
priQueue queue = new priQueue();
for (int i = 0; i < nums.length; i++) {
if(i<k-1)
{
queue.push(nums[i]);
}else {
queue.push(nums[i]);
res.add(queue.max());
queue.pop(nums[i+1-k]);
}
}
int[] r = new int[res.size()];
for (int i = 0; i < res.size(); i++) {
r[i] = res.get(i);
}
return r;
}
// public int[] maxSlidingWindow(int[] nums, int k) {
//
// PriorityQueue<Integer> queue = new PriorityQueue<>((a,b)-> {return b-a;});
// ArrayList<Integer> res = new ArrayList<>();
// for (int i = 0; i < nums.length; i++) {
// if(queue.size()<k)
// {
// queue.add(nums[i]);
// }
// if(queue.size()==k)
// {
// res.add(queue.peek());
// queue.remove(nums[i+1-k]);
// }
// }
// int[] r = new int[res.size()];
// for (int i = 0; i < res.size(); i++) {
// r[i] = res.get(i);
// }
// return r;
// }
}
public class Problem239 {
public static void main(String[] args) throws IOException {
String path = Problem239.class.getResource("data.txt").getPath();
FileReader data = new FileReader(new File(path));
StringBuilder sb = new StringBuilder();
char[] buffer = new char[1024*8];
while (data.read(buffer)!=-1)
{
sb.append(buffer);
}
System.out.println(buffer);
System.out.println(sb.length());
String[] split = sb.toString().split(",");
System.out.println(split.length);
int[] nums = new int[101087];
for (int i = 0; i < nums.length; i++) {
nums[i] = Integer.parseInt(split[i]);
}
Solution239 s = new Solution239();
int k = 50000;
int[] ints = s.maxSlidingWindow(nums, k);
System.out.println(Arrays.toString(ints));
System.out.println("test");
}
}