-
Notifications
You must be signed in to change notification settings - Fork 0
/
Jianz040.java
41 lines (40 loc) · 1.27 KB
/
Jianz040.java
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
import java.util.ArrayList;
import java.util.Stack;
public class Jianz040 {
//1.双栈
public static ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
ArrayList<Integer> res = new ArrayList<>();
if(k == 0) return res;
Stack<Integer> stack1 = new Stack<>();
Stack<Integer> stack2 = new Stack<>();
int index = 0;
for (int i = 0; i < input.length; i++) {
int tmp = input[i];
if(stack1.isEmpty()) {
stack1.add(tmp);
index++;
}else{
while(!stack1.isEmpty()){
if(tmp < stack1.peek()){
stack2.add(stack1.pop());
index--;
}else{
break;
}
}
if(index < k){
stack1.add(tmp);
index++;
}
while(index < k && !stack2.isEmpty()){
stack1.add(stack2.pop());
index++;
}
stack2.clear();
}
}
while(!stack1.isEmpty()) stack2.add(stack1.pop());
while(!stack2.isEmpty()) res.add(stack2.pop());
return res;
}
}