Time:2019/4/16
Title: Sliding Window Maximum
Difficulty: Difficulty
Author: 小鹿
題目:Sliding Window Maximum
Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position. Return the max sliding window.
給定一個(gè)數(shù)組 nums,有一個(gè)大小為 k 的滑動(dòng)窗口從數(shù)組的最左側(cè)移動(dòng)到數(shù)組的最右側(cè)荆残。你只可以看到在滑動(dòng)窗口 k 內(nèi)的數(shù)字。滑動(dòng)窗口每次只向右移動(dòng)一位。
返回滑動(dòng)窗口最大值。
Example:
Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7]
Explanation:
Window position Max
--------------- -----
[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
Note:
You may assume k is always valid, 1 ≤ k ≤ input array's size for non-empty array.
Follow up:
Could you solve it in linear time?
Solve:
▉ 問(wèn)題分析
暴力破解法
1)看到這個(gè)題目最容易想到的就是暴力破解法锣吼,借助一個(gè) for 循環(huán),兩個(gè)變量蓝厌,整體移動(dòng)窗口玄叠,然后每移動(dòng)一次就在大小為 k 的窗口求出最大值。
2)但是這樣的解決效率非常低拓提,如果數(shù)據(jù)非常大時(shí)读恃,共有 n1 個(gè)數(shù)據(jù),窗口大小為 n2(n1 遠(yuǎn)遠(yuǎn)大于 n2),時(shí)間復(fù)雜度為 n2(n1 - n2) 狐粱。也就是 n1 * n2舀寓,最壞時(shí)間復(fù)雜度為 n^2。
優(yōu)先級(jí)隊(duì)列
1)每次移動(dòng)窗口求最大值肌蜻,以及在動(dòng)態(tài)數(shù)據(jù)中求最大值互墓,我們想到的就是優(yōu)先級(jí)隊(duì)列,而優(yōu)先級(jí)隊(duì)列的實(shí)現(xiàn)是堆這種數(shù)據(jù)結(jié)構(gòu)蒋搜,這道題用堆解決效率更高篡撵。如果對(duì)堆不熟悉,趕緊給自己補(bǔ)補(bǔ)功課吧豆挽!底部有我寫(xiě)的文章鏈接育谬。
2)通過(guò)堆的優(yōu)化,向堆中插入數(shù)據(jù)時(shí)間復(fù)雜度為 logn 帮哈,所以時(shí)間復(fù)雜度為 nlogn膛檀。
▉ 算法思路
暴力破解法:
1)用兩個(gè)指針,分別指向窗口的起始位置和終止位置娘侍,然后遍歷窗口中的數(shù)據(jù)咖刃,求出最大值;向前移動(dòng)兩個(gè)指針憾筏,然后操作嚎杨,直到遍歷數(shù)據(jù)完成位置。
優(yōu)先級(jí)隊(duì)列:
1)需要維護(hù)大小為 k 的大頂堆氧腰,堆頂就是當(dāng)前窗口最大的數(shù)據(jù)枫浙,當(dāng)移動(dòng)窗口時(shí),如果插入的數(shù)據(jù)大于堆頂?shù)臄?shù)據(jù)古拴,將其加入到結(jié)果集中箩帚。同時(shí)要?jiǎng)h除數(shù)據(jù),如果刪除的數(shù)據(jù)為最大數(shù)據(jù)且插入的數(shù)據(jù)小于刪除的數(shù)據(jù)時(shí)斤富,向大小為 k 的以 logn 的時(shí)間復(fù)雜度插入膏潮,返回堆頂元素。
▉ 暴力破解法
var maxSlidingWindow = function(nums, k) {
if(k > nums.length || k === 0) return [];
let res = [], maxIndex = -1;
for(let l = 0, r = k-1;r < nums.length;l++, r++){
if(maxIndex < l){
// 遍歷求出最大值
let index = l;
for(let i = l;i <= r;i++) {
if(nums[i] > nums[index]) index = i;
}
maxIndex = index;
}
if(nums[r] > nums[maxIndex]){
maxIndex = r;
}
res.push(nums[maxIndex]);
}
return res;
};
▉ 優(yōu)先級(jí)隊(duì)列
let count = 0;
let heap = [];
let n = 0;
var maxSlidingWindow = function(nums, k) {
let pos = k;
n = k;
let result = [];
let len = nums.length;
// 判斷數(shù)組和最大窗口樹(shù)是否為空
if(nums.length === 0 || k === 0) return result;
// 建大頂堆
let j = 0
for(;j < k; j++){
insert(nums[j]);
}
result.push(heap[1]);
// 移動(dòng)窗口
while(len - pos > 0){
if(nums[k] > heap[1]){
result.push(nums[k]);
insert(nums[k]);
nums.shift();
pos++;
}else{
if(nums.shift() === heap[1]){
removeMax();
}
insert(nums[k-1]);
result.push(heap[1]);
pos++;
}
}
return result;
};
// 插入數(shù)據(jù)
const insert = (data) =>{
//判斷堆滿
// if(count >= n) return; // >=
// 插入到數(shù)組尾部
count++
heap[count] = data;
//自下而上堆化
let i = count;
while(i / 2 > 0 && heap[i] > heap[parseInt(i/2)]){
swap(heap,i,parseInt(i/2));
i = parseInt(i/2);
}
}
// 兩個(gè)數(shù)組內(nèi)元素交換
swap = (arr,x,y) =>{
let temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
// 堆的刪除
const removeMax = () =>{
// 判斷堆空
if(count <= 0) return ;
// 最大數(shù)據(jù)移到最后刪除
heap[1] = heap[count];
// 長(zhǎng)度減一
count--;
// 刪除數(shù)據(jù)
heap.pop();
// 從上到下堆化
heapify(heap,count,1);
}
// 從上到下堆化
const heapify = (heap,count,i) =>{
while(true){
// 存儲(chǔ)堆子節(jié)點(diǎn)的最大值下標(biāo)
let maxPos = i;
// 左子節(jié)點(diǎn)比父節(jié)點(diǎn)大
if(i*2 < n && heap[i*2] > heap[i]) maxPos = i*2;
// 右子節(jié)點(diǎn)比父節(jié)點(diǎn)大
if(i*2+1 <= n && heap[i*2+1] > heap[maxPos]) maxPos = i*2+1;
// 如果沒(méi)有發(fā)生替換满力,則說(shuō)明該堆只有一個(gè)結(jié)點(diǎn)(父節(jié)點(diǎn))或子節(jié)點(diǎn)都小于父節(jié)點(diǎn)
if(maxPos === i) break;
// 交換
swap(heap,maxPos,i);
// 繼續(xù)堆化
i = maxPos;
}
}
▉ 性能分析
暴力破解法
- 時(shí)間復(fù)雜度:O(n^2).
- 空間復(fù)雜度:O(1).
優(yōu)先級(jí)隊(duì)列
- 時(shí)間復(fù)雜度:nlogn.
- 空間復(fù)雜度:O(1).
▉ 擴(kuò)展
堆:
1)堆插入焕参、刪除操作
2)如何實(shí)現(xiàn)一個(gè)堆?
3)堆排序
4)堆的應(yīng)用
詳細(xì)查看寫(xiě)的另一篇關(guān)于堆的文章:數(shù)據(jù)結(jié)構(gòu)與算法之美【堆】
歡迎一起加入到 LeetCode 開(kāi)源 Github 倉(cāng)庫(kù)油额,可以向 me 提交您其他語(yǔ)言的代碼叠纷。在倉(cāng)庫(kù)上堅(jiān)持和小伙伴們一起打卡,共同完善我們的開(kāi)源小倉(cāng)庫(kù)潦嘶!
Github:https://github.com/luxiangqiang/JS-LeetCode
歡迎關(guān)注我個(gè)人公眾號(hào):「一個(gè)不甘平凡的碼農(nóng)」涩嚣,記錄了自己一路自學(xué)編程的故事。