- Notifications
You must be signed in to change notification settings - Fork24
Open
Labels
Description
单调队列
1.维护一个单调递减队列，从大到小，左边是出口，右边是入口
2.每次 pop 时需要判断当前队列是否为空，并且如果当前要弹出的数值等于队列出口元素时，队列移除出口元素
3.每次 push 的元素如果大于入口元素，将队列后端的数值弹出，直到 push 的元素数值小于队列入口元素，保证单调性
4.max 可以获取当前队列的最大值
constmaxSlidingWindow=function(nums,k){constn=nums.lengthclassslideWindow{constructor(){this.data=[]}push(val){letdata=this.datawhile(data.length>0&&data[data.length-1]<val){data.pop()}data.push(val)}pop(val){letdata=this.dataif(data.length>0&&data[0]===val){data.shift()}}max(){returnthis.data[0]}}letres=[]letwindows=newslideWindow()for(leti=0;i<n;i++){if(i<k-1){windows.push(nums[i])}else{windows.push(nums[i])res.push(windows.max())windows.pop(nums[i-k+1])}}returnres}
- 时间复杂度：O(n)
- 空间复杂度：O(n)