劍指Offer_程式設計題——滑動視窗的最大值
題目描述：
給定一個數組和滑動視窗的大小，找出所有滑動視窗裡數值的最大值。例如，如果輸入數組{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]}。
具體要求:
時間限制： C/C++ 1秒，其他語言2秒
空間限制： C/C++32M，其他語言64M
具體實作：
背景知識介紹：
在做題之前，我們首先給大家介紹隊列中的雙端隊列。 我們知道普通隊列是限制級的一端進，另一端出的FIFO形式，棧是一端進出的LIFO形式，而雙端隊列就沒有這樣的限制級，也就是我們可以在隊列兩端進行插入或者删除操作。 通常情況下，隊列的内部都是采用數組來實作，而且帶有兩個指針head和tail來指向數組的區間段，為了充分利用數組空間，我們也會用%來實作邏輯上的循環數組，如下圖。
思路一：
根據我們上面對雙向隊列的解釋，另外題目也說的很明白，是以，我們首先想到的就是采用雙端隊列，其時間複雜度為O(n)。隊列的開頭儲存着目前隊列最大值的指針，當隊列移動一位時：先判斷指針是否超出目前邊界；新加入指針和最後隊列最後的元素比較，剔除小于新加入指針對應位置的值得指針。我們可以通過java和python兩種方式将其實作：
1、首先我們用java将其實作：
import java.util.*;
public class Solution{
public ArrayList<Integer> maxInWindows(int []num, int size){
ArrayList<Integer> res = new ArrayList<>();
int len = num.length;
if(num == null || len < 1 || size < 1 || size > len)
return res;
LinkedList<Integer> llist = new LinkedList<>();
for(int i = 0; i < len; i++){
while(!llist.isEmpty() && num[llist.peekLast()] < num[i])
llist.pollLast();
llist.addLast(i);
if(llist.peekFirst() == i - size){
llist.pollFirst();
}
if (i >= size - 1){
res.add(num[llist.peekFirst()]);
}
}
return res;
}
}
代碼效果圖如圖所示：
2、接下來我們用python将其實作：
class Solution:
def maxInWindows(self, num, size):
if size == 0 or len(num) == 0:
return []
q = []
result = []
for i in range(len(num)):
print('current q', q)
if len(q) > 0:
if(i - q[0]) > (size - 1):
q.pop(0)
while len(q) > 0 and num[i] >= num[q[-1]]:
q.pop(-1)
q.append(i)
if i >= size - 1:
result.append(num[q[0]])
return result
思路二：
仍然是用到思路一中的雙向隊列，不過我們加入了Deque容器，隊列中隻存放目前元素的下标，設新來的元素為k，如果前面的元素比k小，直接把前面的删除（因為不可能成為後面視窗的最大值），如果前面的元素比k大，判斷是否還在視窗範圍内，不在則移除；首先先判斷目前隊列是否為空，如果不空而且目前元素比隊列中尾端的元素大，将隊列元素的尾端彈出；最後判斷隊列頭元素（存的是下标）是否還在滑動視窗範圍中，不在則把頭元素移除；具體我們用java實作如下：
import java.util.*;
public class Solution{
public ArrayList<Integer> maxInWindows(int []num, int size){
ArrayList<Integer> arr = new ArrayList<>();
if (num == null)
return arr;
if(num.length < size || size <= 0)
return arr;
Deque<Integer> queue = new LinkedList<>();
for(int i = 0; i < num.length; i++){
while(!queue.isEmpty() && num[i] >= num[queue.getLast()]){
queue.pollLast();
}
while(!queue.isEmpty() && queue.getFirst() < i - (size - 1))
queue.pollFirst();
queue.offerLast(i);
if(i + 1 >= size)
arr.add(num[queue.getFirst()]);
}
return arr;
}
}
思路三：
昨天我們在做資料流中的中位數的時候，用到了優先隊列(PriorityQueue),并且給大家詳解介紹了優先隊列的用法，如果大家不懂得可以看這篇文章。本題，我們也可以用優先隊列。通過生成javabean方法，其中包括：set、get方法來實作堆排序，具體可以在滑動視窗滑動時，将目前元素加入最大堆（PriorityQueue）中，堆頂的元素即是最大值，同時還要判斷目前元素是否存在于目前視窗中，不存在的話彈出，最後就把該元素添加入Arraylist。我們用java将其實作：
import java.util.*;
class tmp{
public tmp(){
}
public tmp(Integer num, Integer pos){
this.pos = pos;
this.num = num;
}
public Integer pos;
public Integer num;
public Integer getNum() {
return num;
}
public void setNum(Integer num) {
this.num = num;
}
public Integer getPos() {
return pos;
}
public void setPos(Integer pos) {
this.pos = pos;
}
}
public class Solution{
public ArrayList<Integer> maxInWindows(int [] num, int size){
ArrayList<Integer> arr = new ArrayList<>();
if(num == null)
return arr;
if(num.length < size || size <= 0)
return arr;
PriorityQueue<tmp> q = new PriorityQueue<>(100, new Comparator<tmp>(){
public int compare(tmp o1, tmp o2){
return o2.num - o1.num;
}
});
for(int i = 0; i < size - 1; i++)
q.offer(new tmp(num[i], i));
for(int i = size - 1; i < num.length; i++){
q.offer(new tmp(num[i], i));
tmp p = q.peek();
while(p.getPos() < i - (size - 1)){
q.poll();
p = q.peek();
}
arr.add(p.getNum());
}
return arr;
}
}
思路四：
本題可以定義一個求最大值的max函數，視窗每一次滑動求視窗内最大值，時間複雜度O（n*size）。視窗的滑動過程中數字的進出類似一個隊列中元素的出隊入隊，這裡我們采用一個隊列queue存儲可能成為最大值的元素下标(之是以隊列中存元素下标而不是元素值本身，是因為隊列并不存儲所有元素，而我們需要知道什麼時候隊首元素已經離開滑動視窗)。當遇到一個新數時，将它與隊尾元素比較，如果大于隊尾元素，則丢掉隊尾元素，繼續重複比較，直到新數小于隊尾元素，或者隊列為空為止，将新數下标放入隊列。同時需要根據滑動視窗的移動判斷隊首元素是否已經離開。例如：下面以{2,3,6,2,1,7,3,1,5,2}，大小為4的視窗模拟過程：
算法的實作如下，最好的情況是當數組降序排列，此時新數永遠比隊尾元素大，直接存入隊列，時間複雜度為O(n),最壞的情況是當數組是升序排列，此時新數永遠比隊列中所有元素都大，每次都需要清空隊列，時間複雜度為O(nk)。空間複雜度是O(k).我們具體用python将其實作：
class Solution:
def maxInWindows(self, num, size):
maxqueue = []
maxlist = []
n = len(num)
if n == 0 or size == 0 or size > n:
return maxlist
for i in range(n):
if len(maxqueue) > 0 and i - size >= maxqueue[0]:
maxqueue.pop(0)
while len(maxqueue) > 0 and num[i] > num[maxqueue[-1]]:
maxqueue.pop()
maxqueue.append(i)
if i >= size - 1:
maxlist.append(num[maxqueue[0]])
return maxlist
思路五：
該思路其實也是在思路四的基礎上進行的改進，思路四是自己定義一個求最大值max函數。其實python中就有max函數，我們可以直接利用max函數計算其函數值。具體用python實作如下：
class Solution:
def maxInWindows(self, num, size):
if size > len(num) or size == 0:
return []
result = []
for i in range(len(num)):
if (i+size) > len(num):
break
current_win = num[i:i+size]
value = max(current_win)
result.append(value)
return result
思路六：
其實我們也可以用一種最簡單最暴力的方法。每移動一次，周遊數組擷取最大值。但是時間複雜度太高。接下來我們分别用java和python将其實作：
import java.util.*;
public class Solution{
public ArrayList<Integer> maxInWindows(int [] num, int size){
ArrayList<Integer> list = new ArrayList<>();
int len = num.length;
if(num == null || len < 1 || size < 1 || size > len)
return list;
for(int i = size - 1; i < len; i++){
int max = getMaxInWindows(num, i - size + 1, i, size);
list.add(max);
}
return list;
}
public int getMaxInWindows(int []num, int start, int end, int size){
int max = num[start];
for(int i = start + 1; i <= end; i++){
if(num[i] > max){
max = num[i];
}
}
return max;
}
}
2、接下來用python将其實作：
class Solution:
def maxInWindows(self, num, size):
if size <= 0:
return []
res = []
for i in range(0, len(num)-size+1):
res.append(max(num[i:i+size]))
return res