滑動(dòng)窗口最大值
描述
給定一個(gè)數(shù)組 nums，有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)。
你只可以看到在滑動(dòng)窗口內(nèi)的 k 個(gè)數(shù)字?；瑒?dòng)窗口每次只向右移動(dòng)一位。
返回滑動(dòng)窗口中的最大值。
示例
輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:
滑動(dòng)窗口的位置 最大值
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
來(lái)源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/sliding-window-maximum
題解
暴力破解
思路
遍歷每個(gè)滑動(dòng)窗口，在每個(gè)滑動(dòng)窗口中獲取最大值；
代碼
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
if (n * k == 0) return new int[0];
int [] output = new int[n - k + 1];
for (int i = 0; i < n - k + 1; i++) {
int max = Integer.MIN_VALUE;
for(int j = i; j < i + k; j++)
max = Math.max(max, nums[j]);
output[i] = max;
}
return output;
}
復(fù)雜度分析
時(shí)間復(fù)雜度： 在nums數(shù)組中遍歷獲得滑動(dòng)窗口O(N)，在滑動(dòng)窗口中獲取最大值的時(shí)間復(fù)雜度為O(k),
因?yàn)槊恳淮伪闅v數(shù)組獲取滑動(dòng)窗口都需獲取滑動(dòng)窗口的最大值，
因此最終的時(shí)間復(fù)雜度為O(N*k);
空間復(fù)雜度：返回值所需O(N-l+1);
優(yōu)先隊(duì)列
思路
使用大頂堆來(lái)維護(hù)滑動(dòng)窗口中的的數(shù)據(jù)，大頂堆的堆頂元素即為滑動(dòng)窗口中最大值。
算法步驟：
- 準(zhǔn)備：
- 源數(shù)據(jù)nums數(shù)組，長(zhǎng)度為N
- 滑動(dòng)窗口大小k
- 優(yōu)先隊(duì)列（大頂堆）priorityQueue，大小需為k
- 結(jié)果數(shù)組results，長(zhǎng)度為N-k+1
- 初始化priorityQueue：由于滑動(dòng)窗口是從nums的下標(biāo)k-1開(kāi)始遍歷的,因此先
使用nums中[0,k-1]上的值來(lái)初始化priorityQueue;
nums[0,k-1]為第一個(gè)滑動(dòng)窗口，因此results[0]為此時(shí)priorityQueue的最優(yōu)先元素； - 遍歷nums：從k到N遍歷nums，下標(biāo)為i,此時(shí)滑動(dòng)窗口范圍為nums[i-k+1,i],priorityQueue
的值為nums[i-k,i-1]； - 調(diào)整優(yōu)先隊(duì)列：將nums[i]添加到priorityQueue，nums[i-k],從priorityQueue移除，
保持priorityQueue的值與滑動(dòng)窗口的值一致； - 添加滑動(dòng)窗口最大值：優(yōu)先隊(duì)列的隊(duì)首元素為滑動(dòng)窗口此時(shí)的最大值，
results[i-k+1]=priorityQueue的隊(duì)首元素；
代碼
public class PriorityQueueSolution {
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2-o1;
}
};
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (k > len || k < 1) {
return new int[0];
}
int[] result = new int[len - k + 1];
PriorityQueue<Integer> queue = new PriorityQueue<>(k, comparator);
//初始化優(yōu)先隊(duì)列
int i = 0;
while (i < k - 1) {
queue.add(nums[i]);
i++;
}
//從滑動(dòng)窗口中獲取最大值
for (int right = k - 1; right < len; right++) {
queue.add(nums[right]);
if (queue.size() > k) {
queue.remove(nums[right-k]);
}
result[right - k + 1] = queue.element();
}
return result;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度： 在nums數(shù)組中遍歷獲得滑動(dòng)窗口O(N)，優(yōu)先隊(duì)列刪除、添加元素的復(fù)雜度為O(logk),
獲取優(yōu)先隊(duì)列的隊(duì)首元素的時(shí)間復(fù)雜度為O(1),
因此最終的時(shí)間復(fù)雜度為O(N*logk);
空間復(fù)雜度：返回值所需O(N-l+1),優(yōu)先隊(duì)列為O(k),最終為O(N);
雙端隊(duì)列
思路
使用雙端隊(duì)列來(lái)存儲(chǔ)滑動(dòng)窗口在nums中對(duì)應(yīng)的下標(biāo)；
雙端隊(duì)列限制：
- 靠近尾部的隊(duì)列元素的值需要比靠近隊(duì)首的元素的值要大，
即當(dāng)窗口滑動(dòng)時(shí)，滑動(dòng)窗口中增加的元素在nums的下標(biāo)是從隊(duì)尾添加的，
滑動(dòng)窗口移除的元素在nums中的下標(biāo)是從隊(duì)首移除的； - 靠近尾部的隊(duì)列元素的值作為下標(biāo)在nums值需要比靠近隊(duì)首的要小，
即當(dāng)隊(duì)列添加下標(biāo)之前要從隊(duì)列隊(duì)尾去除這些下標(biāo)（它們?cè)趎ums中對(duì)應(yīng)的值要比要添加
下標(biāo)在nums中的要小）；
經(jīng)過(guò)上述限制，隊(duì)列的隊(duì)首下標(biāo)在nums中對(duì)應(yīng)的值始終是隊(duì)列的最大值，即為滑動(dòng)窗口中的最大值；
代碼
public class DequeSolution {
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (k > len || k < 1) {
return new int[0];
}
int[] result = new int[len - k + 1];
//用于存儲(chǔ)在滑動(dòng)窗口中有效的索引，且雙端隊(duì)列會(huì)從前向后維護(hù)一個(gè)降序的排列，
// 獲取滑動(dòng)窗口中的最大值，只需要獲取雙端隊(duì)列的首值即可
Deque<Integer> indexDeque = new ArrayDeque<>(k);
for (int i = 0; i < len; i++) {
addAndRemove(nums, indexDeque, i, k);
if (i >= k - 1) {
result[i - k + 1] = nums[indexDeque.getFirst()];
}
}
return result;
}
private void addAndRemove(int[] nums, Deque<Integer> indexDeque, int index, int k) {
//如果indexDeque中的開(kāi)始元素的索引在當(dāng)前滑動(dòng)窗口的范圍之外刪除
if (indexDeque != null && indexDeque.size() > 0 && (index - indexDeque.getFirst()) > k - 1) {
indexDeque.removeFirst();
}
//循環(huán)從indexDeque后部取出索引indexLast，與要添加的索引index，將它們?cè)趎ums中的值比較，若值indexLast的值比較小，
// 則將indexLast從indexDeque刪除，這樣可以保證indexDeque中的索引在nums中的取值是降序排列，也能保證indexDeque中的
// 首個(gè)值是滑動(dòng)窗口的最大值的索引
while (indexDeque != null && indexDeque.size() > 0 && nums[index] > nums[indexDeque.getLast()]) {
indexDeque.removeLast();
}
indexDeque.addLast(index);
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度： 在nums數(shù)組中遍歷獲得滑動(dòng)窗口O(N)，雙端隊(duì)列刪除、獲取隊(duì)首元素的復(fù)雜度為O(1);添加元素的復(fù)雜度為O(1)~O(logk),
因此最終的時(shí)間復(fù)雜度為O(N)~O(log(k));
空間復(fù)雜度：返回值所需O(N-l+1),雙端隊(duì)列為O(k),最終為O(N);
動(dòng)態(tài)規(guī)劃
思路
構(gòu)造left,right數(shù)組；
- 將nums按k的大小分成多段，最后一段可能不到k個(gè)元素；
- left數(shù)組中，left中按分段與nums對(duì)應(yīng)，left分段中從左到右對(duì)應(yīng)索引的值，是nums對(duì)應(yīng)分段中對(duì)應(yīng)索引及之前的索引的之中最大的一個(gè)值
- right數(shù)組中，right中按分段與nums對(duì)應(yīng)，right分段中從右到左對(duì)應(yīng)索引的值，是nums對(duì)應(yīng)分段中對(duì)應(yīng)索引及之前的索引的之中最大的一個(gè)值
- 因此獲取一個(gè)滑動(dòng)窗口的最大值，是max(滑動(dòng)窗口最左邊位置的索引在right數(shù)組中的值,滑動(dòng)窗口最右邊位置的索引在left數(shù)組中的值
代碼
public class DynamicProgrammingSolution implements ISolution {
@Override
public int[] maxSlidingWindow(int[] nums, int k) {
int len = nums.length;
if (k > len || k < 1) {
return new int[0];
}
int[] left=new int[len];
int[] right=new int[len];
//構(gòu)造left、right數(shù)組
for(int i=0;i<len;i++){
//left構(gòu)造
if(i%k==0){
left[i]=nums[i];
}else{
left[i]=Math.max(left[i-1],nums[i]);
}
//right構(gòu)造,從nums數(shù)組右邊開(kāi)始遍歷
int index=len-i-1;
if(index==len-1||(index+1)%k==0){
right[index]=nums[index];
}else{
right[index]=Math.max(right[index+1],nums[index]);
}
}
//獲取滑動(dòng)窗口最大值數(shù)組
int[] result=new int[len-k+1];
for(int i=0;i<len-k+1;i++){
result[i]=Math.max(right[i],left[i+k-1]);
}
return result;
}
}
復(fù)雜度分析
時(shí)間復(fù)雜度： 構(gòu)造left，rigt數(shù)組O(N),在nums數(shù)組中遍歷獲得滑動(dòng)窗口O(N).
因此最終的時(shí)間復(fù)雜度為O(2N);
空間復(fù)雜度：返回值所需O(N-l+1),left,right數(shù)組分別為O(N),最終為O(3N);
