题目描述:
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]
示例 2：
输入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
输出: [null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= $10^5$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public static int[] maxSlidingWindow(int[] nums, int k) {
int[] ret = new int[nums.length - k + 1];
LinkedList<Integer> queue = new LinkedList<>();
for (int i = 0; i < nums.length; i++) {
while (!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]) {
queue.pollLast();
}
queue.offerLast(i);
if (queue.peek() <= i - k) {
queue.poll();
}
if (i + 1 >= k) {
ret[i + 1 - k] = nums[queue.peek()];
}
}
return nums;
}
|
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1
示例 1：
输入:
[“MaxQueue”,“push_back”,“push_back”,“max_value”,“pop_front”,“max_value”]
[[],[1],[2],[],[],[]]
输出:[null,null,null,2,1,2]
示例 2：
输入:
[“MaxQueue”,“pop_front”,“max_value”]
[[],[],[]]
输出:[null,-1,-1]
限制：
1 <= push_back,pop_front,max_value的总操作数<= 10000
1 <= value <= $10^5$
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
| class MaxQueue {
private int head = 0;
private int tail = 0;
private int n = 99999;
private int[] items = new int[n];
private Deque<Integer> deque;
public MaxQueue() {
deque = new LinkedList<>();
}
public int max_value() {
if (deque.isEmpty()) {
return -1;
}
return deque.peekFirst();
}
public void push_back(int value) {
if ((tail + 1) % n == head) return;
while (!deque.isEmpty() && deque.peekLast() < value) {
deque.pollLast();
}
items[tail] = value;
tail = (tail + 1) % n;
deque.offerLast(value);
}
public int pop_front() {
if (head == tail) return -1;
int ret = items[head];
items[head] = 0;
head = (head + 1) % n;
if (ret == deque.peekFirst()) {
deque.pollFirst();
}
return ret;
}
}
|
这道算法题不再是编写一个函数方法，而是写一个类，所以示例一时间不好理解。多看几次示例能看出，第一个数字除第一个是初始化实例外，后面都是调用该实例的对应方法，而第二是输入的参数，调用无参函数则是[]。
为方便大家提交算法时，用例测试错误不好调试代码，写了一份 JAVA 反射代码来方便运行测试用例 用法:第一行字符串数组把固定的 「MaxQueue」 删掉，对应的删掉第二参数的第一个「[]」，再去掉首位的方括号复制到 methods 数组的初始化值;为方便我把参数列表实例化成 int 数组，可以复制第二行到编辑器（VSCode 等），先批量替换「[]」为「-1」，再把「[」和「]」都批量去除（也就是替换那栏不填任何东西），然后复制替换好的字符串到以下 params 数组的数组的初始化值，然后就可以运行了。
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
|
public static void main(String[] args) {
String[] methods = new String[]{"pop_front", "pop_front", "pop_front", "pop_front", "pop_front", "push_back", "max_value", "push_back", "max_value"}
int[] params = new int[]{-1, -1, -1, -1, -1, 15, -1, 9, -1};
try {
Object clazz = Class.forName("MaxQueue").newInstance();
Method max_value = clazz.getClass().getDeclaredMethod("max_value");
Method pop_front = clazz.getClass().getDeclaredMethod("pop_front");
Method push_back = clazz.getClass().getDeclaredMethod("push_back", int.class);
List<Integer> integers = new ArrayList<>();
int size = methods.length;
for (int i = 0; i < size; i++) {
String method = methods[i];
switch (method) {
case "max_value":
integers.add((Integer) max_value.invoke(clazz));
break;
case "pop_front":
integers.add((Integer) pop_front.invoke(clazz));
break;
case "push_back":
push_back.invoke(clazz, params[i]);
integers.add(null);
break;
default:
break;
}
}
System.out.println(Arrays.toString(integers.toArray()));
} catch (ClassNotFoundException e) {
e.printStackTrace();
} catch (IllegalAccessException e) {
e.printStackTrace();
} catch (InstantiationException e) {
e.printStackTrace();
} catch (NoSuchMethodException e) {
e.printStackTrace();
} catch (InvocationTargetException e) {
e.printStackTrace();
}
System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1,3,-1,-3,5,3,6,7},3)));
}
|
