g***j
发帖数: 1275 | 1 如果不看答案，直接写的出来线性解的答案么？ 电话面试。 | l*****a
发帖数: 14598 | 2 这个镇的算基本题了,连我都会
两重循环再加上细节处理就OK
int start=0;
while(1) {
end=start;
while(end<***) {
insert value of end into DS
if meet requirement ,break;
end++;
}
if (end== ) break;
while(start
remove value of start
if not meet requirement ,break;
start++;
}
}
【在 g***j 的大作中提到】
: 如果不看答案，直接写的出来线性解的答案么？ 电话面试。
| x******0
发帖数: 178 | 3 虽然是老题，但是写起来还是很费劲，唉。。
public static ArrayList SlidingWindowMax(int[] arr, int windowSize){
//edge case
ArrayList res = new ArrayList();
ArrayDeque indexQ = new ArrayDeque();
for (int i = 0; i < windowSize; i++){
while (!indexQ.isEmpty() && arr[i] > indexQ.getLast()){
indexQ.pollLast();//only keep possible max
}
indexQ.add(i);
}
for (int i = windowSize; i
res.add(arr[indexQ.peek()]);
while (!indexQ.isEmpty() && arr[i] > arr[indexQ.getLast()]){
indexQ.pollLast();
}
if (!indexQ.isEmpty() && indexQ.peek() <= i-windowSize){//reach
the window
indexQ.poll();
}
indexQ.add(i);
}
//last one
res.add(arr[indexQ.peek()]);
return res;
} |
|
