題目一：滑動窗口的最大值初婆。
給定一個數組和滑動窗口的大小序厉，找出所有滑動窗口里數值的最大值轿衔。例如，如果輸入數組{2,3,4,2,6,2,5,1}及滑動窗口的大小3浪谴，那么一共存在6個滑動窗口开睡，他們的最大值分別為{4,4,6,6,6,5}祈搜； 針對數組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}士八， {2,3,[4,2,6],2,5,1}容燕， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}婚度， {2,3,4,2,6,[2,5,1]}蘸秘。
練習地址
https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788
https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
參考答案
import java.util.ArrayList;
import java.util.LinkedList;
public class Solution {
public ArrayList<Integer> maxInWindows(int[] num, int size) {
ArrayList<Integer> result = new ArrayList<>();
if (num == null || num.length == 0 || size < 1 || size > num.length) {
return result;
}
LinkedList<Integer> list = new LinkedList<>();
for (int i = 0; i < size; i++) {
while (!list.isEmpty() && num[list.getLast()] <= num[i]) {
list.removeLast();
}
list.add(i);
}
for (int i = size; i < num.length; i++) {
result.add(num[list.getFirst()]);
while (!list.isEmpty() && num[list.getLast()] <= num[i]) {
list.removeLast();
}
if (!list.isEmpty() && i - list.getFirst() >= size) {
list.removeFirst();
}
list.add(i);
}
result.add(num[list.getFirst()]);
return result;
}
}
在上述代碼中，list是一個兩端開口的隊列蝗茁，用來保存有可能是滑動窗口最大值的數字的下標醋虏。
在存入一個數字的下標之前，首先要判斷隊列里已有數字是否小于待存入的數字哮翘。如果已有的數字小于待存入的數字颈嚼，那么這些數字已經不可能是滑動窗口的最大值，因此它們將會被依次從隊列的尾部刪除（調用函數removeLast()）饭寺。
同時阻课，如果隊列頭部的數字已經從窗口里滑出，那么滑出的數字也需要從隊列的頭部刪除（調用函數removeFirst()）艰匙。
由于隊列的頭部和尾部都有可能刪除數字限煞，這也是需要兩端開口的隊列的原因。
復雜度分析
- 時間復雜度：O(n)员凝。
- 空間復雜度：O(k)署驻。k為滑動窗口大小。
題目二：隊列的最大值
請定義一個隊列并實現函數max得到隊列里的最大值健霹，要求函數max旺上、push和pop的時間復雜度都是O(1)。
練習地址
https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
參考答案
class MaxQueue {
private LinkedList<Integer> queue, maxQueue;
public MaxQueue() {
queue = new LinkedList<>();
maxQueue = new LinkedList<>();
}
public int max_value() {
return maxQueue.isEmpty() ? -1 : maxQueue.getFirst();
}
public void push_back(int value) {
queue.add(value);
while (!maxQueue.isEmpty() && value > maxQueue.getLast()) {
maxQueue.removeLast();
}
maxQueue.add(value);
}
public int pop_front() {
if (queue.isEmpty()) {
return -1;
}
int value = queue.removeFirst();
if (value == maxQueue.getFirst()) {
maxQueue.removeFirst();
}
return value;
}
}
復雜度分析
- 時間復雜度：O(1)糖埋。
- 空間復雜度：O(1)宣吱。
