Open azl397985856 opened 2 years ago
var maxSlidingWindow = function (nums, k) {
const queue = [];
const res = [];
for (let i = 0; i < k; i++) {
mantainQueue(queue, i);
}
res.push(nums[queue[0]]);
for (let i = k; i < nums.length; i++) {
mantainQueue(queue, i);
if (queue[0] <= i - k) {
queue.shift();
}
res.push(nums[queue[0]]);
}
return res;
function mantainQueue(queue, i) {
while (queue.length && nums[i] > nums[queue[queue.length - 1]]) {
queue.pop();
}
queue.push(i);
}
};
/* 复杂度
时间 O(n)
空间 O(k)
*/
这个题用暴力解法会超时TLE。 可以使用MaxHeap(优先队列)来做此题,时间复杂度是 O(n log k)。
而使用双端队列,有办法实现时间复杂度为 O(n)。 题目中的 Follow up 要求我们代码的时间复杂度为 O(n),所以只好使用双端队列了。
我们先回到题目的提示部分吧:
隐藏提示1 How about using a data structure such as deque (double-ended queue)?
隐藏提示2
The queue size need not be the same as the window’s size.
隐藏提示3
Remove redundant elements and the queue should store only elements that need to be considered.
于是我们按提示试试双端队列
deque + 滑动窗口, 其实还需要用单调队列来做。
维护1个单调队列(deque),deque中存储的是当前窗口最大值的索引,维护操作: 保持单调递减,队头是最大值
。
对于窗口中的每个数而言,不断地把左侧比自己小的数从队列中删掉, 遇到下一个比自己大的数时自己会被删掉。遇到比自己小的数得留着,最终双端队列会成为递减队列。
实现语言: C++
class Solution {
public:
vector<int> res;
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> indexQ; // 双端队列,存储的是当前窗口最大值的索引,维护操作: 保持单调递减,队头是最大值
for (int i = 0; i < nums.size(); i++) {
// 依次地将数组元素加入到队列中
// 注意: 确保队列元素间的距离都在k以内
if (!indexQ.empty() && i - k + 1 > indexQ.front()) /* 倒着数第k个与队列开头数的index比较。窗口长度>k时,从队列中删掉最前面的数 */
indexQ.pop_front();
while (!indexQ.empty() && nums[i] >= nums[indexQ.back()])
indexQ.pop_back(); /* 不断地把左侧比自己小的数从队列中删掉, 遇到下一个比自己大的数时自己会被删掉。遇到比自己小的数得留着,最终双端队列会成为递减队列。 */
indexQ.push_back(i);
if (i >= k - 1) // 只要窗口大小 ≥ k 时, 窗口就会有最大值,将其放进res(结果vector)中
{
res.push_back(nums[indexQ.front()]);
}
}
return res;
}
};
class Solution {
public:
vector
使用优先队列的方法进行查找
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
Time Complexity: O(nlogn)
Space Complexity: O(n)
用堆自动排序,同时及时移出已经不在滑动窗口内的点
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
import heapq
hp=[]
ans=[]
for i in range(k):
heapq.heappush(hp,(-nums[i],i))
ans.append(-hp[0][0])
for i in range(k,len(nums)):
heapq.heappush(hp,(-nums[i],i))
while hp[0][1]<i-k+1:
heapq.heappop(hp)
ans.append((-hp[0][0]))
return ans
时间复杂度:O(nlogn),对每个值均进行堆插入
空间复杂度:O(n),堆的大小
用优先队列可以让时间复杂度降为O(n),空间复杂度降为O(k)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q=deque()
q.append(0)
ans=[]
if k==1:
ans.append(nums[0])
for i in range(1,len(nums)):
if q[0]==i-k:
q.popleft()
while len(q)>0 and nums[i]>nums[q[-1]]:
q.pop()
q.append(i)
if i>=k-1:
ans.append(nums[q[0]])
return ans
用单调栈保持可能最大的元素
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
import collections
index_queue = collections.deque()
result = []
for i in range(len(nums)):
while index_queue and nums[i] >= nums[index_queue[-1]]:
index_queue.pop()
while index_queue and i - index_queue[0] >= k:
index_queue.popleft()
index_queue.append(i)
if i >= k - 1:
result.append(nums[index_queue[0]])
return result
时间复杂度 :O(N)
空间复杂度:O(k)
var maxSlidingWindow = function(nums, k) { const n = nums.length; const q = []; for (let i = 0; i < k; i++) { while (q.length && nums[i] >= nums[q[q.length - 1]]) { q.pop(); } q.push(i); }
const ans = [nums[q[0]]];
for (let i = k; i < n; i++) {
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
q.push(i);
while (q[0] <= i - k) {
q.shift();
}
ans.push(nums[q[0]]);
}
return ans;
};
Sliding window + mono queue O(n) and O(k)
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
l, ret = 0, []
N = len(nums)
queue = deque()
for r in range(N):
while r - l + 1 > k:
if queue[0] <= l:
queue.popleft()
l += 1
n = nums[r]
while queue and n > nums[queue[-1]]:
queue.pop()
queue.append(r)
if r-l+1 == k:
ret.append(nums[queue[0]])
return ret
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] result = new int[nums.length - k + 1];
Deque<Integer> deque = new ArrayDeque<>();
for (int i = 0; i < nums.length; i++){
if (!deque.isEmpty() && deque.peekFirst() + k <= i) deque.pollFirst();
while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]){
deque.pollLast();
}
deque.offerLast(i);
if (i - k + 1 >= 0) result[i - k + 1] = nums[deque.peekFirst()];
}
return result;
}
}
Time Complexity: O(n), Space Complexity: O(1)
双端队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums.length < k) return new int[0];
if (k == 1) return nums;
int[] res = new int[nums.length - k + 1];
Deque<Integer> queue = new ArrayDeque<Integer>();
for (int i = 0; i < nums.length; i++) {
if (!queue.isEmpty() && queue.peekFirst() + k <= i) queue.pollFirst();
while (!queue.isEmpty() && nums[queue.peekLast()] < nums[i]) queue.pollLast();
queue.offerLast(i);
if (i + 1 >= k) res[i + 1 - k] = nums[queue.peekFirst()];
}
return res;
}
}
var maxSlidingWindow = function(nums, k) {
if(k * nums.length === 0) return [];
if(k === 1) return nums;
var i;
var queue = new myQueue();
var result = [];
for (i = 0; i < k; i++) {
queue.push(nums[i]);
}
result.push(queue.front());
for (; i < nums.length; i++) {
queue.pop(nums[i - k]);
queue.push(nums[i]);
result.push(queue.front());
}
return result;
};
var myQueue = function() {
this.head;
this.tail;
}
myQueue.prototype.push = function(v) {
while (this.tail && this.tail.val < v) {
var temp = this.tail;
this.tail = this.tail.prev;
delete temp;
}
var newNode = {val: v, prev: null, next: null};
if(this.tail) {
newNode.prev = this.tail;
this.tail.next = newNode;
this.tail = newNode;
} else {
//there is no node left in the queue
this.head = newNode;
this.tail = this.head;
}
}
myQueue.prototype.pop = function(v) {
if(v === this.front()) {
var temp = this.head;
this.head = this.head.next;
if(this.head) this.head.prev = null;
delete temp;
}
}
myQueue.prototype.front = function() {
return this.head.val;
}
class Solution(object):
def maxSlidingWindow(self, nums, k):
# queue
result = []
queue = deque()
for i in range(len(nums)):
while queue and nums[queue[-1]]<nums[i]:
queue.pop()
queue.append(i)
while i-queue[0]>=k:
queue.popleft()
if i >= k-1:
result.append(nums[queue[0]])
return result
class Solution(object):
result = []
h = []
heapq.heapify(h)
for i in range(k):
heapq.heappush(h,[-nums[i], i])
i = k
window_left = 0
window_right = k-1
while window_right < len(nums):
[local_big_value, index] = h[0]
if window_left <= index <= window_right:
result.append(-local_big_value)
else:
while h[0][1] < window_left:
heapq.heappop(h)
[local_big, index] = h[0]
result.append(-local_big)
window_left += 1
window_right += 1
if window_right == len(nums):
return result
heapq.heappush(h, [-nums[window_right], window_right])
思路:
滑动窗口法, 窗口宽度k, 使用辅助空间-双端队列(double ended queue)或者数组(vector)记录元素的下标
复杂度分析:
时间复杂度: O(n), n为数组nums的元素数 空间复杂度: O(k), k为窗口宽度
代码(C++):
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
if (n <= 1 || k <= 1) return nums;
deque<int> idx;
vector<int> res;
for (int i = 0; i < n; ++i) {
if (!idx.empty() && (i - idx.front() + 1) > k)
idx.pop_front();
while (!idx.empty() && nums[i] >= nums[idx.back()])
idx.pop_back();
idx.push_back(i);
if (i >= k - 1) res.push_back(nums[idx.front()]);
}
return res;
}
};
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
LinkedList<Integer> queue = new LinkedList<>(); //index
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++){
while(!queue.isEmpty() && nums[i] >= nums[queue.peekLast()]){
queue.pollLast();
}
queue.addLast(i);
if (queue.peek() <= i - k){
queue.poll();
}
if (i-k + 1 >= 0){
res[i - k + 1] = nums[queue.peek()];
}
}
return res;
}
}
很巧妙
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> queue = new PriorityQueue<>((p1, p2) -> p1[0] != p2[0] ? p2[0] - p1[0] : p2[1] - p1[1]);
for (int i = 0; i < k; i++) {
queue.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = queue.peek()[0];
for (int i = k; i < n; i++) {
queue.offer(new int[]{nums[i], i});
while (queue.peek()[1] <= i - k) {
queue.poll();
}
ans[i - k + 1] = queue.peek()[0];
}
return ans;
}
}
复杂度分析
令 n 为数组长度。
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
Deque<Integer> q = new LinkedList<>();
int index = 0;
for (int i = 0; i < nums.length; i++) {
while (!q.isEmpty() && nums[q.peekLast()] <= nums[i]) {
q.pollLast();
}
q.add(i);
if (q.peekFirst() == i - k) {
q.pollFirst();
}
if (i >= k - 1) {
res[index++] = nums[q.peekFirst()];
}
}
return res;
}
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
if not nums: return []
# 单调队列:只保留可能成为最大值的数,如果小,则pop()
queue = []
for i in range(k):
while queue and queue[-1] < nums[i]:
queue.pop()
queue.append(nums[i])
res = [queue[0]]
for i in range(k, len(nums)):
if nums[i-k] == queue[0]:
queue.pop(0)
while queue and queue[-1] < nums[i]:
queue.pop()
queue.append(nums[i])
res.append(queue[0])
return res
滑动窗口,单调队列
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> q = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
if (!q.isEmpty() && i - q.getFirst() >= k)
q.pollFirst();
while (!q.isEmpty() && nums[i] > nums[q.getLast()])
q.pollLast();
q.addLast(i);
if (i >= k-1)
res[i-k+1] = nums[q.getFirst()];
}
return res;
}
}
单调递减queue 如果queue的左边已经不在window里面popleft
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
result = []
queue = deque()
for i in range(len(nums)):
while queue and queue[-1][0] <= nums[i]:
queue.pop()
queue.append((nums[i], i))
if i >= k - 1:
while queue and queue[0][1] <= i - k:
queue.popleft()
result.append(queue[0][0])
return result
时间复杂度O(n)
空间复杂度O(k)
python
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = collections.deque() # decreasing queue, store max index of curr window
res = []
for i, num in enumerate(nums):
while q and num > nums[q[-1]]:
q.pop()
q.append(i)
if q[0] <= i - k:
q.popleft()
if i >= k - 1:
res.append(nums[q[0]])
return res
# deque: storing index of candidate of current window
# remove all elements that's smaller than current num from the deque
# append the num
# remove all elements that has index out of lef boundary of curr window
# d[0] is the index of max value in curr window
# time: O(N), every num is processed twice
# space: O(k)
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
deq = deque()
res = []
for i, num in enumerate(nums):
# remove elements thats smaller than num
while deq and nums[deq[-1]] <= num:
deq.pop()
deq.append(i)
while deq[0] <= i - k:
deq.popleft()
if i >= k - 1:
res.append(nums[deq[0]])
return res
单调递减队列
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
queue = []
res=[]
for i,num in enumerate(nums):
while queue and nums[queue[-1]]<=num:
queue.pop()
queue.append(i)
if queue[0]<=i-k:
queue.pop(0)
if i>=k-1:
res.append(nums[queue[0]])
return res
时间复杂度: O(N) 空间复杂度: O(k)
C++ Code:
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<pair<int,int>> que;
/// decrease que
// sliding window [i, i+k-1]
vector<int> ret;
for(int i=0; i<k; i++)
{
while(que.size() && que.back().first<=nums[i])
{
que.pop_back();
}
que.push_back(make_pair(nums[i], i));
}
ret.push_back(que.front().first);
for(int i=1; i<=nums.size()-k ; i++)
{
while(que.size() && que.front().second<i)
{
que.pop_front();
}
while(que.size() && que.back().first<=nums[i+k-1])
{
que.pop_back();
}
que.push_back(make_pair(nums[i+k-1], i+k-1));
ret.push_back(que.front().first);
}
return ret;
}
};
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int length = nums.length;
Deque<Integer> queue = new ArrayDeque<>();
int[] res = new int[length - k + 1];
for (int i = 0 , j = 0; i < length; i++) {
while (!queue.isEmpty() && i- k + 1 > queue.getFirst())
queue.pollFirst();
while (!queue.isEmpty() && nums[i] > nums[queue.getLast()])
queue.pollLast();
queue.offer(i);
if( i - k + 1 >= 0)
res[j++] = nums[queue.getFirst()];
}
return res;
}
}
动态求极值,所以可以想到用堆排序。 但是还得检测一下堆里的最大数字到底在不在窗口里。所以要存数组的索引,同时用数组值来排序。 取值时先判断最大值在不在窗口里。如果不在,出列再找下一个最大的,直到最大值在窗口里。
/**
* @param {number[]} nums
* @param {number} k
* @return {number[]}
*/
var maxSlidingWindow = function(nums, k) {
let ans = [];
const pQ = new MaxPriorityQueue({ priority: (idx) => nums[idx] });
let l = 0;
for (let r=0; r<nums.length; r++) {
pQ.enqueue(r);
if (r >= k-1) {
// console.log(pQ.toArray());
while (pQ.front().element < l) {
// not in window
pQ.dequeue();
}
ans.push(nums[pQ.front().element]);
l++;
}
}
return ans;
};
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<vector<int>, vector<vector<int>>> pq;// (val, indx)
int curMax = INT_MIN;
vector<int> res;
for(int i = 0;i < nums.size();i++) {
pq.push({nums[i],i});
if(i - k + 1 >= 0) {
while(i - k + 1 > pq.top()[1]) {
pq.pop();
}
res.push_back(pq.top()[0]);
}
}
return res;
}
};
https://leetcode.com/problems/sliding-window-maximum/
const maxSlidingWindow = function (nums, k) {
const q = []; // stores *indices*
const res = [];
for (let i = 0; i < nums.length; i++) {
while (q && nums[q[q.length - 1]] <= nums[i]) {
q.pop();
}
q.push(i);
// remove first element if it's outside the window
if (q[0] === i - k) {
q.shift();
}
// if window has k elements add to results (first k-1 windows have < k elements because we start from empty window and add 1 element each iteration)
if (i >= k - 1) {
res.push(nums[q[0]]);
}
}
return res;
};
time O(n) space O(k)
单调队列
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> que;
vector<int> ans;
for(int ii = 0; ii < nums.size(); ++ ii){
int jj = ii - k + 1;
if(!que.empty() &&que.front() < jj) que.pop_front();
while(!que.empty() && nums[que.back()] <= nums[ii]){
que.pop_back();
}
que.push_back(ii);
if(ii >= k - 1){
ans.push_back(nums[que.front()]);
}
}
return ans;
}
};
n为数组长度。
https://leetcode.com/problems/sliding-window-maximum/
const maxSlidingWindow = function (nums, k) {
const q = []; // stores *indices*
const res = [];
for (let i = 0; i < nums.length; i++) {
while (q && nums[q[q.length - 1]] <= nums[i]) {
q.pop();
}
q.push(i);
if (q[0] === i - k) {
q.shift();
}
add 1 element each iteration)
if (i >= k - 1) {
res.push(nums[q[0]]);
}
}
return res;
};
time O(n) space O(k)
变化的最大值→堆
deque存储index便于移除出window元素
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = collections.deque()
ans = []
for i in range(len(nums)):
# 单调递减
while q and nums[q[-1]] < nums[i]:
q.pop()
# window内
while q and i - q[0] >= k:
q.popleft()
q.append(i)
if i>=k-1:
ans.append(nums[q[0]])
return ans
Using a maxheap, when heap.size == k; maxValue = heap.peek; Iterate through the array, heap remove the leftmost element (nums[i-k]), and add nums[I] in heap
public int[] maxSlidingWindow(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>(Collections.reverseOrder());
int n = nums.length;
int [] res = new int[n - k + 1];
for(int i = 0; i< k; i++) {
heap.add(nums[i]);
}
res[0] = heap.peek();
for(int i = k ; i < nums.length; i++) {
heap.remove(nums[i - k]);
heap.add(nums[i]);
res[i - k + 1] = heap.peek();
}
return res;
}
from collections import deque class Solution: def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':
n = len(nums)
if n * k == 0:
return []
if k == 1:
return nums
def clean_deque(i):
# remove indexes of elements not from sliding window
if deq and deq[0] == i - k:
deq.popleft()
# remove from deq indexes of all elements
# which are smaller than current element nums[i]
while deq and nums[i] > nums[deq[-1]]:
deq.pop()
# init deque and output
deq = deque()
max_idx = 0
for i in range(k):
clean_deque(i)
deq.append(i)
# compute max in nums[:k]
if nums[i] > nums[max_idx]:
max_idx = i
output = [nums[max_idx]]
# build output
for i in range(k, n):
clean_deque(i)
deq.append(i)
output.append(nums[deq[0]])
return output
思路
优先队列
代码
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int length = nums.length;
Deque<Integer> queue = new ArrayDeque<>();
int[] res = new int[length - k + 1];
for (int i = 0 , j = 0; i < length; i++) {
while (!queue.isEmpty() && i- k + 1 > queue.getFirst())
queue.pollFirst();
while (!queue.isEmpty() && nums[i] > nums[queue.getLast()])
queue.pollLast();
queue.offer(i);
if( i - k + 1 >= 0)
res[j++] = nums[queue.getFirst()];
}
return res;
}
}
复杂度
时间复杂度:O(N)
空间复杂度:O(N)
使用单调队列保存窗口中的值,当新加入的值大于队列尾部时,循环弹出队尾元素,当移除的元素等于队列头部时,弹出队头元素
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> queue = new LinkedList<>();
int l = 0, r = 0;
for (r = 0; r < k; ++r) {
while (!queue.isEmpty() && nums[r] > queue.peekLast()) {
queue.pollLast();
}
queue.offer(nums[r]);
}
--r;
int[] ans = new int[nums.length - k + 1];
ans[0] = queue.peek();
while (r + 1 < nums.length) {
if (nums[l] == queue.peek()) {
queue.poll();
}
++l;
++r;
while (!queue.isEmpty() && nums[r] > queue.peekLast()) {
queue.pollLast();
}
queue.offer(nums[r]);
ans[l] = queue.peek();
}
return ans;
}
}
借鉴了Deque法
Deque. Firstly, update first k elements in deque. To push the element into the deque, it should follow such rules:
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: 'List[int]', k: 'int') -> 'List[int]':
n = len(nums)
if n * k ==0:
return []
if k == 1:
return nums
def clean_deque(i):
if dq and dq[0] == i-k:
dq.popleft()
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq = deque()
max_id = 0
for i in range(k):
clean_deque(i)
dq.append(i)
if nums[i] > nums[max_id]:
max_id = i
ans=[nums[max_id]]
for i in range(k,len(nums)):
clean_deque(i)
dq.append(i)
ans.append(nums[dq[0]])
return ans
Time: O(n) Space: O(n)
AC
//heap
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int[] res = new int[nums.length - k + 1];
if(nums.length == 1) return nums;
PriorityQueue<int[]> heap = new PriorityQueue<>((o1, o2) -> o2[0]-o1[0]);
for(int i = 0;i < k;i++){
int[] cur = new int[]{nums[i], i};
heap.add(cur);
}
int right = k-1;
for(int i = 0;i < nums.length-k+1;i++){
while(heap.peek()[1] < i){
heap.poll();
}
int[] max = heap.peek();
res[i] = max[0];
if(++right < nums.length){
int[] rightItem = new int[]{nums[right], right};
heap.add(rightItem);
}
}
return res;
}
}
//双指针
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums.length == 1) return nums;
Deque<Integer> deq = new LinkedList<>();
for(int i = 0;i < k;i++){
prep(deq, nums, 0, i,k);
deq.add(i);
}
int[] res = new int[nums.length - k + 1];
res[0] = nums[deq.getFirst()];
for(int left = 0, right = k;right < nums.length;right++,left++){
prep(deq, nums, left, right,k);
deq.add(right);
res[left+1] = nums[deq.getFirst()];
}
return res;
}
public void prep(Deque<Integer> deq, int[] nums, int left, int right, int k){
// System.out.println(right + " b " + deq);
if(!deq.isEmpty() && deq.getFirst() == left && right >= k){
deq.removeFirst();
}
while(!deq.isEmpty() && nums[right] > nums[deq.getLast()]){
deq.removeLast();
}
// System.out.println(right + " a " + deq);
}
}
//heap time: O(NlogN) space: O(N)
//双指针 time: O(N) space: O(N)
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
w = deque()
left = right = 0
while right < len(nums):
while w and nums[w[-1]] < nums[right]:
w.pop()
w.append(right)
if left > w[0]:
w.popleft()
if right+1 >= k:
res.append(nums[w[0]])
left += 1
right += 1
return res
Credit to [NeetCode][https://www.youtube.com/watch?v=DfljaUwZsOk]
Time: O(N)
Space: O(N)
啊=-=花了快两个小时,一早上就没了。 结论还是没写出来。自己试了暴力最后超时,尝试堆,但是发现堆要排序,于是又莫得了。 最后理解单调队列,按理来说应该和单调栈一样,只是这里维护的是索引。 该队列的核心是,front是最大的。新加入的数要for循环不断与tail比较,若比tail大,则移除tail添加 <-维护优先队列的逻辑 生成一个输出数组,从i=k开始遍历,先push(i),然后for循环判断当前的队列头的索引是否在i-k区间内,若不是,则移除队列头到范围内,最后添加nums
func maxSlidingWindow(nums []int, k int) []int {
q := []int{}
push := func(i int){
for len(q) > 0 && nums[i] >= nums[q[len(q)-1]]{
q = q[:len(q)-1]
}
q = append(q,i)
}
for i:=0; i < k;i++{
push(i)
}
n := len(nums)
out := make([]int,1,n-k+1)
out[0] = nums[q[0]]
for i:=k; i < n; i++{
push(i)
for q[0] <= i-k{
q =q[1:]
}
out = append(out,nums[q[0]])
}
return out
}
时间复杂度O(n) 空间复杂度O(k)
Language: Java
public int[] maxSlidingWindow(int[] nums, int k) {
// Use a deque to keep indices of monotone stack of valued in the window
Deque<Integer> deque = new LinkedList<>();
int[] result = new int[nums.length - k + 1];
for (int i = 0; i < nums.length; i++) {
// Remove the index out of the current window
while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
deque.pollFirst();
}
// Remove indices of values smaller than nums[i] to maintain monotonicity
while(!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
deque.pollLast();
}
deque.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[deque.peekFirst()];
}
}
return result;
}
没思路所以看官解
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
q = deque()
res = []
for i in range(len(nums)):
while q and nums[i] >= nums[q[-1]]:
q.pop()
while q and i - q[0] == k:
q.popleft()
q.append(i)
if i >= k - 1:
res.append(nums[q[0]])
return res
Time: O (N)
Space: O (k)
参考学习
var maxSlidingWindow = function (nums, k) {
// 队列数组(存放的是元素下标,为了取值方便)
const q = [];
// 结果数组
const ans = [];
for (let i = 0; i < nums.length; i++) {
// 若队列不为空,且当前元素大于等于队尾所存下标的元素,则弹出队尾
while (q.length && nums[i] >= nums[q[q.length - 1]]) {
q.pop();
}
// 入队当前元素下标
q.push(i);
// 判断当前最大值(即队首元素)是否在窗口中,若不在便将其出队
while (q[0] <= i - k) {
q.shift();
}
// 当达到窗口大小时便开始向结果中添加数据
if (i >= k - 1) ans.push(nums[q[0]]);
}
return ans;
};
语言:C++
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> q;
vector<int> res;
for (int i = 0; i < nums.size(); i++) {
if (q.size() && i - k + 1 > q.front()) q.pop_front();
while (q.size() && nums[i] >= nums[q.back()]) q.pop_back();
q.push_back(i);
if (i >= k - 1) res.push_back(nums[q.front()]);
}
return res;
}
};
class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
new_arr=[]
max_num=deque()
for i,n in enumerate(nums):
while max_num and nums[max_num[-1]]<=n:
max_num.pop()
max_num +=[i]
if i-max_num[0]>=k:
max_num.popleft()
if i+1>=k:
new_arr.append(nums[max_num[0]])
return new_arr
Time: O(n)
Space: O(k)
维护一个优先队列,让优先队列作为滑动窗口,改写优先队列的排序规则,让滑动窗口的最大值在队列的头部,当滑动窗口长度到达k时,就将队列头部出队,然后再维护一个新的滑动窗口
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> queue = new PriorityQueue<>((a1,a2)-> a1[0] != a2[0] ? a2[0] - a1[0] : a2[1] - a1[1]);
int[] ans = new int[n - k + 1];
for(int i = 0; i < k ;i++){
queue.offer(new int[]{nums[i],i});
}
ans[0] = queue.peek()[0];
for(int i = k;i < n;i++){
queue.offer(new int[]{nums[i],i});
while(queue.peek()[1] <= i - k){
queue.poll();
}
ans[i - k + 1] = queue.peek()[0];
}
return ans;
}
}
时间复杂度:O(nlogn)
空间复杂度:O(n)
滑动窗口
,堆(优先队列)
Go Code:
func maxSlidingWindow(nums []int, k int) []int {
var res, q []int
for i, num := range nums {
for len(q) != 0 && q[len(q)-1] < num {
q = q[:len(q)-1]
}
q = append(q, num)
if i < k-1 {
continue
}
res = append(res, q[0])
if nums[i-k+1] == q[0] {
q = q[1:]
}
}
return res
}
复杂度分析
令 n 为数组长度。
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int, int>> q;
for (int i = 0; i < k; ++i) {
q.emplace(nums[i], i);
}
vector<int> ans = {q.top().first};
for (int i = k; i < n; ++i) {
q.emplace(nums[i], i);
while (q.top().second <= i - k) {
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
class Solution:
def maxSlidingWindow(self, nums, k):
''' method 1 brute force, TimeLimitExceed now'''
if not nums:
return []
res = []
for i in range(len(nums)):
if i + k <= len(nums):
res.append(max(nums[i:i+k]))
return res
''' method 2 deque
单调队列 + 滑动窗口,只存储符合要求的单调递增元素
time complexity O(n) n 是数组长度
space complexity O(k) k 是参数
'''
q = collections.deque()
ans = []
for i in range(len(nums)):
# 将deque[-1] 对应的值和 nums[i] 比较,
# 保证 deque[-1] 中的 index 始终是对应的最大的元素
while q and nums[q[-1]] <= nums[i]:
q.pop()
# 保证 deque 中的第一个元素始终是 sliding window 里面的数
while q and i - q[0] >= k:
q.popleft()
q.append(i)
# 保证 res 添加的是 sliding window 生成后,对应的 deque 中最大的元素
# 经过前面两个 while,q 中有且只有最大的元素
# 注意 q 里面存的只是 index,
if i >= k - 1:
ans.append(nums[q[0]])
return ans
s = Solution()
print(s.maxSlidingWindow(nums=[1, 3, -1, -3, 5, 3, 6, 7], k=3))
单调队列。不需要储存窗口内所有的元素。如果新进入的元素比前面的大,可以直接将前面的元素移除。这样每一时刻我们都会得到一个单调递减队列,队首元素为最大值。 具体做法:入队列。然后移除失效元素,包括(1) 超出窗口范围的元素,(2) 队列尾部小于当前值的元素。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
Deque<Integer> queue = new LinkedList<>();
for (int i = 0; i < k; i++) {
while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
queue.pollLast();
}
queue.offerLast(i);
}
int n = nums.length;
int[] res = new int[n - k + 1];
res[0] = nums[queue.peekFirst()];
for (int i = k; i < n; i++) {
while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
queue.pollLast();
}
queue.offerLast(i);
if (queue.peekFirst() < i - k + 1) {
queue.pollFirst();
}
res[i - k + 1] = nums[queue.peekFirst()];
}
return res;
}
}
复杂度分析
class Solution(object):
def maxSlidingWindow(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: List[int]
"""
q = collections.deque([])
res = []
for i in range(len(nums)):
if not q:
q.append(i)
else:
while q and i-q[0]>=k:
q.popleft()
while q and nums[i]>nums[q[-1]]:
q.pop()
q.append(i)
if i >= k-1:
res.append(nums[q[0]])
return res
优先队列 提交
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
priority_queue<pair<int, int>> q;
for(int i=0;i<k;i++)
q.emplace(nums[i],i);
vector<int>ans={q.top().first};
for(int i=k;i<n;++i)
{
q.emplace(nums[i],i);
while(q.top().second<=i-k)
{
q.pop();
}
ans.push_back(q.top().first);
}
return ans;
}
};
复杂度分析
239. 滑动窗口最大值
入选理由
暂无
题目地址
https://leetcode-cn.com/problems/sliding-window-maximum/
前置知识
题目描述
返回滑动窗口中的最大值。
进阶:
你能在线性时间复杂度内解决此题吗?
示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释:
滑动窗口的位置 最大值
[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
提示:
1 <= nums.length <= 10^5 -10^4 <= nums[i] <= 10^4 1 <= k <= nums.length