azl397985856 commented 2 years ago

239. 滑动窗口最大值

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/sliding-window-maximum/

前置知识

队列

滑动窗口

题目描述


给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回滑动窗口中的最大值。

进阶：

你能在线性时间复杂度内解决此题吗？

示例:

输入: 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

MoonLee001 commented 2 years ago

思路

滑动窗口

代码

var maxSlidingWindow = function(nums, k) {
    let res = [];
    const n = nums.length;
    let left = 0, right = k - 1;
    while(right < n) {
        let max = -Infinity;
        let i = left;
        while (i <= right) {
            max = Math.max(max, nums[i]);
            i++;
        }
        res.push(max);
        left++;
        right++;
    }
    return res;
};

复杂度分析

时间复杂度： O(n^2)
空间复杂度： O(n)

rzhao010 commented 2 years ago

Thoughts

Use PriorityQueue to keep track of the maximum in each window, also if the index of the peek value is less then i - k, then we should remove it from the heap

Code

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] != b[0] ? b[0] - a[0] : b[1] - a[1]);
        int[] res = new int[n - k + 1];
        for (int i = 0; i < k; i++) {
            pq.offer(new int[]{nums[i], i});
        }
        res[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();
            }
            res[i - k + 1] = pq.peek()[0];
        }
        return res;
    }
}

Complexity Time: O(nlogn), n for the loop, logn for the offer() operation of heap Space: O(n)

Yongxi-Zhou commented 2 years ago

思路

保持单调队列，每次更新队列的最大值，每次更新队列的最大值的时候，更新结果数组。

代码

    class Solution:
        def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
            q = deque()
            n = len(nums)
            res = []
            for i in range(n):
                # print(q)
                while q and i - q[0] >= k:
                    q.popleft()
                while q and nums[q[-1]] <= nums[i]:
                    q.pop()
                q.append(i)
                if i - k + 1 >= 0:
                    res.append(nums[q[0]])
            return res

复杂度

time O(N) space O(1)

MichaelXi3 commented 2 years ago

Idea

滑动窗口
及时drop超出窗口的index
及时drop小于当先值的index，只保留最大值

deque.peek()的值即为每个window最大值

Code

class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
    // Edge case
    if (nums == null || k <= 0) {
        return new int[0];
    }

    int n = nums.length;
    int[] res = new int[n - k + 1];
    int right = 0;
    // Queue to store index of array
    Deque<Integer> q = new ArrayDeque<>();

    for (int i=0; i<n; i++) {
        // If index out of window, remove it
        if (!q.isEmpty() && q.peek() < i-k+1) {
            q.poll();
        }
        // Only retain the max number within window
        while (!q.isEmpty() && nums[q.peekLast()] < nums[i]) {
            q.pollLast();
        }
        // Add current element
        q.offer(i);
        // Input res
        if (i > k-2) {
            res[right] = nums[q.peek()];
            right++;
        }
    }
    return res;
}
}

Complexity

Time Complexity: O(N)
Space Complexity: O(1)

ZacheryCao commented 2 years ago

Idea

Monotonic Array

Code

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        record = collections.deque()
        ans = []
        i, j = 0, k-1
        for m in range(k):
            while record and nums[m]>record[-1][1]:
                record.pop()
            record.append((m, nums[m]))
        ans.append(record[0][1])
        while j < len(nums)-1:
            i += 1
            j += 1
            while record and i>record[0][0]:
                record.popleft()
            while record and nums[j]>record[-1][1]:
                record.pop()
            record.append((j, nums[j]))
            ans.append(record[0][1])
        return ans

Complexity:

Time: O(N) Space: O(N)

maybetoffee commented 2 years ago

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums == null || nums.length == 0){
            return nums;
        }
        Deque<Integer> queue = new LinkedList<>();
        int[] res = new int[nums.length-k+1];

        for(int i = 0; i < nums.length; i++){
            while(!queue.isEmpty() && nums[queue.peekLast()] < nums[i]){
                queue.pollLast();
            }
            queue.addLast(i);

            if(queue.peek() <= i-k){
                queue.poll();
            }

            if(i+1 >= k){
                res[i+1-k] = nums[queue.peek()];
            }
        }
        return res;
    }
}

houmk1212 commented 2 years ago

思路

滑动窗口中的最值问题，用单调队列来解决。

代码

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        int len = n - k + 1;
        int[] res = new int[len];
        int index = 0;

        LinkedList<Integer> queue = new LinkedList<>();
        for (int i = 0; i < k; i++) {
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.addLast(i);
        }

        if (!queue.isEmpty()) {
            res[index++] = nums[queue.peekFirst()];
        }

        for (int i = k; i < n; i++) {
            while (!queue.isEmpty() && i - k >= queue.peekFirst()) {
                queue.pollFirst();
            }
            while (!queue.isEmpty() && nums[i] > nums[queue.peekLast()]) {
                queue.pollLast();
            }
            queue.addLast(i);
            if (!queue.isEmpty()) {
                res[index++] = nums[queue.peekFirst()];
            }
        }
        return res;
    }
}

复杂度

时间复杂度：O(N) N是数组长度，需要遍历一次数组，每次遍历最多是一次的入队和进队。
空间复杂度：O(N)

zhulin1110 commented 2 years ago

题目地址(239. 滑动窗口最大值)

https://leetcode-cn.com/problems/sliding-window-maximum/

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

前置知识

滑动窗口

思路

见注释

代码

语言支持：JavaScript

JavaScript Code:


/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
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;
};

复杂度分析

令 n 为数组长度。

时间复杂度：O(n)
空间复杂度：O(n)

KelvinG-LGTM commented 2 years ago

思路

单调队列 : 保证一直都是队列最尾巴是当前最大. 每次循环都会保证

单调性

移除窗口外的元素

代码

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
    queue = deque()
    res = []
    for i in range(len(nums)): 
        while queue and nums[queue[-1]] <= nums[i]: queue.pop() # 保证单调性. 
        while queue and i - queue[0] >= k: queue.popleft()  # 保证窗外的元素被移除. 
        queue.append(i)
        if i >= k - 1: 
            res.append(nums[queue[0]])

    return res

复杂度分析

时间复杂度

O(N)

空间复杂度

O(N)

反思

如何能够想出用单调队列来解决问题?

freedom0123 commented 2 years ago

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length < k) return new int[]{};
        int hh = 0 ;
        int tt  = -1;
        int n = nums.length;
        int[] q = new int[n+1];
        List<Integer> list = new ArrayList<>();
        for(int i = 0 ; i < n ;i ++){
            if(hh <= tt && i - k + 1 > q[hh]) hh++;
            while(hh <= tt && nums[q[tt]] <= nums[i]) tt--;
            q[++tt] = i;
            if(i >= k-1) list.add(nums[q[hh]]);
        }
        int[] res = new int[list.size()];
        for(int i = 0 ;i < list.size(); i++) res[i] = list.get(i);
        return res;

    }
}

ShawYuan97 commented 2 years ago

代码

语言支持：Python3

Python3 Code:


class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        每次输出滑动窗口的最大值
        滑动窗口中的值使用一个单调队列(双端队列实现)维护
        如果k大于等于len(nums)，输出数组最大值
        如果k小于len(nums)，输出值个数为len(nums)-k+1
        """
        if k >= len(nums):
            return [max(nums)]
        q = collections.deque()
        ans = []
        for i in range(len(nums)):
            # 保证队列是单调递减的
            while q and nums[q[-1]] <= nums[i]: q.pop() 
            # 保证单调栈长度<=k
            while q and i - q[0] >= k: q.popleft()
            q.append(i)
            if i >= k - 1: ans.append(nums[q[0]])
        return ans

复杂度分析

令 n 为数组长度,k为双端队列长度。

时间复杂度：$O(n)$
空间复杂度：$O(k)$

hyh331 commented 2 years ago

Day28 思路

使用具有单调性的双端队列。在窗口右移时，使用一个队列存储所有没有被移除的下标，并且这些下标从小到大排序。在窗口右移时，需要把一个新的元素放入队列，需要将新元素与队尾元素比较，若新元素>=队尾元素：删除队尾元素，将其弹出队列。不断进行此操作，知道队列为空或新元素<队尾元素。由于队列下标对应的元素是严格单调递减的，因此队首下标对应元素就是滑动窗口中的最大值。

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //使用双向队列。
        vector<int> res;
        deque<int> dq;
        for (int i = 0; i < nums.size(); ++i) {
            //如果窗口长度已经超过了k，则将最左边的元素移除
            if (!dq.empty() && dq.front() == i - k) dq.pop_front();
            //从后往前移除所有队列中小于当前元素的元素
            while (!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();
            //在队列中添加当前元素
            dq.push_back(i);
            //如果窗口长度已经到达了k，则在结果中插入最大值(deque最前面的元素)
            if (i >= k-1) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};

复杂度分析

时间复杂度：O(n)
空间复杂度：O(k)

Geek-LX commented 2 years ago

4.28

思路：

对滑动窗口建立一个大小为 k 的大顶堆。窗口滑动时，从堆中去除一个滑动窗口最前的一个数，添加滑动窗口后一个数。

代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        h=[]
        ans=[]
        for i in range(k):
            heapq.heappush(h,(-nums[i],i))
        ans.append(-h[0][0])
        for i in range(k,len(nums)):
            heapq.heappush(h,(-nums[i],i))
            while h[0][1]<i-k+1:
                heapq.heappop(h)
            ans.append((-h[0][0]))
        return ans

复杂度分析

令 n 为数组长度

时间复杂度: O(nlogk)
空间复杂度: O(k)

biscuit279 commented 2 years ago

思路：

单调队列

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        ans = []
        q = collections.deque() # 保存下标
        for i in range(len(nums)):
            while  q and nums[q[-1]] <= nums[i]:
                q.pop()
            while q and i-q[0] >= k:
                q.popleft()
            q.append(i)
            if i >= k-1:
                ans.append(nums[q[0]])
        return ans

时间复杂度：O(n) 空间复杂度：O(k)

currybeefer commented 2 years ago

思路：使用用链表连接的单调队列就可以解题代码：

class MonotonicQueue
    {
    public:
        list<int> lickedList;
        void push(int n)
        {
            while(!lickedList.empty() && lickedList.back()<n)
            {
                lickedList.pop_back();
            }
            lickedList.push_back(n);
        }
        int max()
        {
           return lickedList.front(); 
        }
        void pop(int n)
        {
            if(lickedList.front()==n)
                lickedList.pop_front();
        }
    };
    vector<int> maxSlidingWindow(vector<int>& nums, int k) 
    {
        vector<int> res;
        MonotonicQueue window;
        for(int i=0;i<k-1;i++)
        {
            window.push(nums[i]);
        }
        for(int i=k-1;i<nums.size();i++)
        {
            window.push(nums[i]);
            res.push_back(window.max());
            window.pop(nums[i-k+1]);
        }
        return res;
    }

时间复杂度：O(n) 空间复杂度：O(k)

wenliangchen commented 2 years ago

Idea

Using Deque

Code

class Solution {
  ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
  int [] nums;

  public void clean_deque(int i, int k) {
    // remove indexes of elements not from sliding window
    if (!deq.isEmpty() && deq.getFirst() == i - k)
      deq.removeFirst();

    // remove from deq indexes of all elements 
    // which are smaller than current element nums[i]
    while (!deq.isEmpty() && nums[i] > nums[deq.getLast()])                           deq.removeLast();
  }

  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n * k == 0) return new int[0];
    if (k == 1) return nums;

    // init deque and output
    this.nums = nums;
    int max_idx = 0;
    for (int i = 0; i < k; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      // compute max in nums[:k]
      if (nums[i] > nums[max_idx]) max_idx = i;
    }
    int [] output = new int[n - k + 1];
    output[0] = nums[max_idx];

    // build output
    for (int i  = k; i < n; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      output[i - k + 1] = nums[deq.getFirst()];
    }
    return output;
  }
}

Serena9 commented 2 years ago

代码

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() # 维持单调性
            while q and i - q[0] >= k: q.popleft() # 移除失效元素
            q.append(i)
            if i >= k - 1: ans.append(nums[q[0]])
        return ans

Jessie725 commented 2 years ago

Idea

Use stack is a sliding window head has the largest element, if the incoming element is larger, remove the head

Code

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> stack = new ArrayDeque<>();
        int[] res = new int[nums.length - k + 1];
        int ri = 0;

        for (int i = 0; i < nums.length; i++) {
            while (!stack.isEmpty() && nums[stack.peekFirst()] < nums[i]) {
                stack.pollFirst();
            }
            stack.offerFirst(i);

            if (i >= k - 1) {
                res[ri++] = nums[stack.peekLast()];
            }

            if (stack.peekLast() == i - k + 1) {
                stack.pollLast();
            }
        }
        return res;
    }
}

Complexity

Time:O(n) Space:O(n)

oneline-wsq commented 2 years ago

思路

利用堆

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        h=[]
        ans=[]
        for i in range(k):
            heapq.heappush(h,(-nums[i],i))
        ans.append(-h[0][0])
        for i in range(k,len(nums)):
            heapq.heappush(h,(-nums[i],i))
            while h[0][1]<i-k+1:
                heapq.heappop(h)
            ans.append((-h[0][0]))
        return ans

时间复杂度：O(log k)

空间复杂度：O(k)

ghost commented 2 years ago

题目

Sliding Window Maximum

思路

Deque

代码

class Solution:
def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
res = []
q = collections.deque()

    for i in range(len(nums)):
        while(q and nums[q[-1]]<nums[i]):
            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

复杂度

Space: O(k) Time: O(n)

577961141 commented 2 years ago

239.滑动窗口最大值

题目链接

https://leetcode-cn.com/problems/sliding-window-maximum/

题目思路

解法一：

暴力解法，这种很容易超时，不推荐

解法二：

双端队列
双指针（固定滑动窗口）

双指针是一个固定为$k的滑动窗口,我们先定义left和right都是从0开始的，然后right一直循环自增（right 超过nums的就停止）， right的每次自增之前，都要把nums[right]加入到优先队列中，在加入到优先队列之前，都要循环的比较优先队列的最后一个数是否是小于nums[right],如果小于的话，就去掉优先队列的最后一个数，直到循环比较到不符合条件为止，这样就能保证优先队列的头部一定是最大值。当right自增到right -left + 1 = k的时候代表着，可以从这个优先队列里面头部的值，加入到要返回的res里面，但是要注意这个优先头部的最大值是否等于nums[left],如果等于的话就需要去掉这个优先队列里面头部的值，以保证下一个滑动窗口比较不会被用到，然后left页进行自增。重复上面的步骤就能求出解

leetleetcode解释：

其实，我们没必须存储窗口内的所有元素。如果新进入的元素比前面的大，那么前面的元素就不再有利用价值，可以直接移除。这提示我们使用一个单调递增栈来完成。

但由于窗口每次向右移动的时候，位于窗口最左侧的元素是需要被擦除的，而栈只能在一端进行操作。而如果你使用普通的数组实现，就是可以在另一端操作了，但是时间复杂度仍然是 O(k)

因此，我们考虑使用链表来实现，维护两个指针分别指向头部和尾部即可，这样做的时间复杂度是 O(1)，这就是双端队列。

因此思路就是用一个双端队列来保存接下来的滑动窗口可能成为最大值的数。

具体做法：

入队列
移除失效元素，失效元素有两种

一种是已经超出窗口范围了，比如我遍历到第 4 个元素，k = 3，那么 i = 0 的元素就不应该出现在双端队列中了。具体就是索引大于 i - k + 1的元素都应该被清除
小于当前元素都没有利用价值了，具体就是从后往前遍历（双端队列是一个递减队列）双端队列，如果小于当前元素就出队列

经过上面的分析，不难知道双端队列其实是一个递减的一个队列，因此队首的元素一定是最大的。用图来表示就是：

题目的题解code

解法一：

class Solution
{

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function maxSlidingWindow($nums, $k)
    {
        $res = [];
        for ($i = 0; $i <= count($nums) - $k; $i++) {
            $cur = $this->maxInSlidingWindow($nums, $i, $i+$k);
            $res[] = $cur;
        }

        return $res;
    }

    /**
     * 获取数组某个区间的最大值
     *
     * @param array $nums 数组
     * @param int $start 开始的索引
     * @param int $end 结束的索引
     * @return mixed
     * @author 陈维锐
     * @date 2022/04/28 9:44
     */
    private function maxInSlidingWindow($nums, $start, $end)
    {
        $max = $nums[$start];
        for ($i = $start; $i < $end; $i++) {
            $max = max($max, $nums[$i]);
        }
        return $max;
    }
}

golang

解法二：

class Solution
{

    /**
     * @param Integer[] $nums
     * @param Integer $k
     * @return Integer[]
     */
    function maxSlidingWindow($nums, $k)
    {
        $left = $right = 0;
        $len = count($nums);
        $queue = new SplQueue();
        $res = [];

        while ($right < $len) {
            $r_num = $nums[$right];
            // 当队列不为空，且队列的最后一个值小于当前的值，那么就移除队列的最后一个值，一直循环下去，到不满足条件为止，确保队列的首个值为最大值
            while (!$queue->isEmpty() && $queue->top() < $r_num) {
                $queue->pop();
            }
            $queue->enqueue($r_num);

            if ($right - $left + 1 == $k) {
                $l_num = $nums[$left];
                $res[] = $queue->bottom();
                // 左边的数等于队列的数说明一个问题，那就是队列是存储滑动窗口最左边的值为最大值，那么在下一次循环的时候，就要去掉在队列中的这个值，防止再次比较这个值
                if ($l_num == $queue->bottom()) {
                    $queue->dequeue();
                }
                $left++;
            }
            $right++;
        }
        return $res;
    }
}

func maxSlidingWindow(nums []int, k int) []int {
    q := []int{}

    push := func(i int) {
        for len(q) > 0 && nums[q[len(q) - 1]] < nums[i] { // 循环去掉最后一项
            q = q[:len(q) -1]
        }
        q = append(q, i)
    }

    for i := 0; i < k; i++ { // 找出前k项最大值的k
        push(i)
    }

    n := len(nums)
    ans := make([]int, 1, n-k+1)
    ans[0] = nums[q[0]]
    for i := k; i < n; i++ {
        push(i)
        if q[0] <= i - k { // 防止重复比较
            q = q[1:]
        }
        ans = append(ans, nums[q[0]])
    }
    return ans
}

时间和空间复杂度

解法一：

时间复杂度：O(n*k)
空间复杂度：O(1)

解法二：

时间复杂度: O(n)
空间复杂度：O(k)

YuyingLiu2021 commented 2 years ago

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:

        if len(nums) ==1:            
            return nums         
        res = []
        queue = collections.deque()
        #https://zhuanlan.zhihu.com/p/46462831
        #deque：类似列表(list)的容器，实现了在两端快速添加(append)和弹出(pop)
        for i, num in enumerate(nums):
            if queue and queue[0] == i - k: #判断一个元素是否从右界变成了左届，并将要pop出去
                queue.popleft()
            while queue and nums[queue[-1]] < num:
                queue.pop()
            queue.append(i)
            if i >= k - 1:
                res.append(nums[queue[0]])
        return res

#         #solution 2 heap
#       # nums = [1, 3, -1, -3, 5, 3, 6, 7]
#       # how to get max value among the window
#       # use maximum heap (-value, index) 

#       # Time complexity : O(NlogN)
#       # Space complexity: O(N)

        # res, heap = [], []
        # for i in range(len(nums)):
        #   heapq.heappush(heap, ( -nums[i], i))
        # #https://blog.csdn.net/brucewong0516/article/details/79042839
        #   if i + 1 >= k:
        #       while heap and heap[0][1] <  i + 1 - k:
        #           heapq.heappop(heap)
        #       res.append(-heap[0][0])
        # return res

caterpillar-0 commented 2 years ago

思路

双端队列，维护一个在k个窗口的单调递减序列，新来值与队尾值比较

代码

class Solution {
public:
    //使用单调队列，双端队列
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        deque<int> q;
        for(int i=0;i<k;i++){
            while(!q.empty() && nums[i]>=nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);      
        }
        vector<int> res;
        res.push_back(nums[q.front()]);
        for(int i=k;i<nums.size();i++){
            while(!q.empty() && nums[i]>=nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
            while(q.front()<=i-k){
                q.pop_front();
            }
            res.push_back(nums[q.front()]);
        }
        return res;
    }
};

复杂度分析

时间复杂度：o(n)
空间复杂度：o(n)

carterrr commented 2 years ago

class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int len = nums.length; int[] res = new int[len - k + 1]; LinkedList<int[]> ll = new LinkedList<>(); for(int r = 0; r < len; r ++ ) { while(!ll.isEmpty() && ll.peekFirst()[0] < nums[r]) { ll.pollFirst(); } if(!ll.isEmpty() && ll.peekLast()[1] < r - k + 1) { ll.pollLast(); } ll.addFirst(new int[]{nums[r], r}); // 最大放在Last 先进队的也放在Last if(r - k + 1 >= 0) res[r - k + 1] = ll.peekLast()[0]; } return res; } }

tensorstart commented 2 years ago

思路

最开始暴力勉强过了，看了题解用的双端队列，js嫌麻烦没有自己造轮子，直接用数组写的

代码

var maxSlidingWindow = function(nums, k) {
    let l=0,r=0;
    let queue=[];
    let res=[];
    while (r<nums.length){
        //空队列直接push
        if (queue.length===0) queue.push(nums[r]);
        //否则比较
        else {
            //队尾大于待插入元素，将待插入元素放入队尾
            if (queue[queue.length-1]>=nums[r]) queue.push(nums[r]);
            //否则，循环判断弹出
            else {
                queue.pop();
                while (queue.length){
                    if (queue[queue.length-1]>=nums[r]){
                        queue.push(nums[r]);
                        break;
                    }
                    queue.pop();
                }
                //如果队列空了，就把nums[r]插入
                if (queue.length===0) queue.push(nums[r]);
            }

        }
        if (r-l+1===k){
            nums[l]===queue[0]?res.push(queue.shift()):res.push(queue[0]);
            r++;l++;

        }else r++;
    }
    return res;
};

复杂度分析

时间O(n) 空间O(n)

TonyLee017 commented 2 years ago

思路

优先队列

代码

def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
  if len(nums) == 1: return nums
    queue = [(-nums[i],i) for i in range(k)]
    heapq.heapify(queue)  #最大堆

    res = [-queue[0][0]]
    for i in range(k,len(nums)):
        heapq.heappush(queue,(-nums[i],i))
        while queue[0][1] <= i-k:
            heapq.heappop(queue)
        res.append(-queue[0][0])
    return res

复杂度分析

时间复杂度：O(nlogn)
空间复杂度：O(n)

physicshi commented 2 years ago

思路

单调递减队列
利用单调队列存下标，头部是区间最大值 max 对应的下标
根据当前下标对应值的大小，把当前下标放到队列合适的位置
只要构成了滑动窗口，就可以把队列最大值（头部）对应的值放到结果数组中

代码

var maxSlidingWindow = function (nums, k) {
  const res = [];
  const queue = [];
  for (let i = 0; i < nums.length; i++) {
    if (i - queue[0] >= k) queue.shift();
    while (nums[queue[queue.length - 1]] <= nums[i]) {
      queue.pop();
    }
    queue.push(i);
    if (i >= k - 1) {
      res.push(nums[queue[0]]);
    }
  }
  return res;
};

复杂度

时间复杂度：O(n)，n 是 nums 的长度，每个元素入队一次
空间复杂度：O(k)，定义了一个辅助队列 queue，最多存放 k 大小的元素

1973719588 commented 2 years ago

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        for i in range(k):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)

        ans = [nums[q[0]]]
        for i in range(k, n):
            while q and nums[i] >= nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0] <= i - k:
                q.popleft()
            ans.append(nums[q[0]])

        return ans

时间复杂度：O(N) 空间复杂度：O(N)

Ellie-Wu05 commented 2 years ago

思路一：暴力求解

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k==1:
            return nums

        n = len(nums)

        ans = [None]*(n-k+1)

        i = 0
        j = k

        while j<=n:
            temp = nums[i:j]
            ans[i] = max(temp)
            i+=1
            j+=1

        return ans

超时

单调递增队列

代码

class maxQueue:

    def __init__(self):
        self.queue = collections.deque()
    def push(self, val):
        # 每次push进value的时候，把比他更小的都pop出去
        while self.queue and val>self.queue[-1]:
            self.queue.pop()
        self.queue.append(val)
    def pop(self):
        # 因为是monotonic max queue，所以popleft就是最大值
        self.queue.popleft()
    def max(self):
        return self.queue[0]

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        if k==1:
            return nums

        n = len(nums)
        ans= []
        q = maxQueue()

        for i in range(n):
            q.push(nums[i])
            # 到达sliding window size 的 maximum
            if i-k+1>=0:
                ans.append(q.max())
                # 如果queue的最大值等于接下来push进来的值，pop掉他，append新值可以和后面的比较
                if nums[i-k+1] == q.max(): q.pop()

        return ans

复杂度

时间：On 空间：On

Magua-hub commented 2 years ago


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()]);//表示当前窗口中至少右k个元素
    }

    return res;
    }
};

zzz607 commented 2 years ago

思路

使用类似单调递减栈的单调减减队列，在该队列最大长度为K，保存每个窗口长度内的最大值及排在该最大值后面的所有较小的值。从而，队列首即为每个窗口内的最大值。

代码


func maxSlidingWindow(nums []int, k int) []int {
    var ret []int

    qq := newMyQueue(k)
    for i := 0; i < len(nums); i++ {
        qq.add(nums[i], i)
        if i >= k - 1 {
            ret = append(ret, qq.peek())
        }
    }

    return ret
}

type dd struct{val int; idx int}
type myQueue struct {
    data []*dd
    win int
}

func newMyQueue(win int) *myQueue {
    return &myQueue{data: []*dd{{val: math.MinInt32, idx: 0}}, win: win}
}

func (q *myQueue) add(val, idx int) {
    // 弹出数组中所有小于val的值
    if idx - q.data[0].idx >= q.win {
        q.data = q.data[1:]
    }

    var i int
    for i = q.len() - 1; i >= 0; i-- {
        if q.data[i].val >= val {
            q.data = q.data[:i + 1]
            break
        }
    }
    if i == -1 {
        q.data = q.data[:0]
    }
    q.data = append(q.data, &dd{val: val, idx: idx})
}

func (q *myQueue) peek() int {
    return q.data[0].val
}

func (q *myQueue) len() int {
    return len(q.data)
}

复杂度分析

时间复杂度：maxSlidingWindow函数中的循环，每个元素都会被访问一次；而每个元素在 q.add函数中最多会有K次循环，所以时间复杂度是 O(nk) ?? 如果一个元素在q.add中会循环 k次，那么，在该元素之前的k个元素，其在q.add函数必须只循环一次，所以摊到每个元素中还是只循环一次，从而q.add可以认为是一个 O(1) 的操作。最终，时间复杂度为 O(N)
空间复杂度：O(K)

yinhaoti commented 2 years ago

class Solution:

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        Ideas:
            Sliding Windows + Brute-Force
        TC: O(n * k)
        SC: O(1)
        Improve: heap
        """
        ans = []

        for i in range(len(nums) - k + 1):
            max_value = max(nums[i:i+k])
            ans.append(max_value)
        return ans

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        Ideas: heap -> max heap
            insert into new num, pop out if cur_max out of windows
        TC: O(nlogk)
        SC: O(k)
        Improve: monostack
        """
        import heapq 
        heap = []
        for i in range(k):
            heapq.heappush(heap, (-1 * nums[i], i))

        ans = [-1 * heap[0][0]]
        for i in range(k, len(nums)):
            heapq.heappush(heap, (-1 * nums[i], i))
            while heap[0][1] < i - k + 1:
                heapq.heappop(heap)
            ans.append(-1 * heap[0][0])
        return ans

    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        """
        Ideas: Decreasing Mono-queue -> get cur_max within size-k:
            with max-k size queue -> only save cur max to cur element -> decreasing mono-queue / increasing mono-stack
        TC: O(n)
        SC: O(n)
        Ref: https://github.com/azl397985856/leetcode/blob/master/problems/239.sliding-window-maximum.md
        """
        q = collections.deque()
        ans = []

        for i in range(len(nums)):
            if q and i - q[0][0] >= k: q.popleft()
            while q and q[-1][1] < nums[i]: q.pop()
            q.append((i, nums[i]))
            # print(q)
            if i >= k - 1: ans.append(q[0][1])
        return ans

LyuliangLiu commented 2 years ago

Idea

Deque, poll smaller numbers from rear. Make it a decreasing queue. Deque should store index, because can get number from the nums[] with the index.

Code

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        Deque<Integer> q = new LinkedList<>();
        Deque<Integer> index = new LinkedList<>();
        int i = 0;
        int[] max = new int[nums.length - k + 1];
        for (; i < k; i++) {
            while (!q.isEmpty() && q.peekLast() <= nums[i]) {
                q.pollLast();
                index.pollLast();
            }
            q.offerLast(nums[i]);
            index.offerLast(i);
        }
        while (i < nums.length) {
            max[i - k] = q.peekFirst();
            if (index.peekFirst() <= i - k) {
                index.pollFirst();
                q.pollFirst();
            }
            while (!q.isEmpty() && q.peekLast() <= nums[i]) {
                q.pollLast();
                index.pollLast();
            }
            q.offerLast(nums[i]);
            index.offerLast(i);
            i++;
        }
        max[nums.length - k] = q.poll();
        return max;
    }
}

Complexity

Time: O(n). Space: O(k)

flaming-cl commented 2 years ago

Code

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
var maxSlidingWindow = function(nums, k) {
  const q = [];
  const res = [];
  for (let i = 0; i < nums.length; i++) { // move the sliding window to the right hand side
    // kick out the last element of our current queue: when the last one is smaller than the iterating element, that means the last element is impossible to be the biggest number
    while (q.length && nums[i] >= nums[q[q.length - 1]]) {
      q.pop();
    }

    // push the index of the iterating element into our queue 
    q.push(i);

    // adjust our sliding window——kick out the top element from our queue: index of the top element in our queue <= index of the leftmost element of our sliding window
    while (q[0] <= i - k) {
      q.shift();
    }

    // i >= k - 1 ，we reached the target sliding window size，push the largest number of the current sliding window to our answer array
      if (i >= k - 1) res.push(nums[q[0]]);
  }
  return res;
};

Complexity

Time：O(N)
Space：O(K)

JasonHe-WQ commented 2 years ago

思路：完全不会，看了答案答案的意思是：构建一个递减的序列，每当一个数要进入时，不断判断是不是比当前最小值小，如果不，从后往前pop，为了移动窗口，每当一个数进来后，判断左侧第一个是不是应该pop，然后答案队列append当前最大值代码：

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        q = collections.deque()
        for i in range(k):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
        ans = [nums[q[0]]]
        for i in range(k,n):
            while q and nums[i]>=nums[q[-1]]:
                q.pop()
            q.append(i)
            while q[0]<=i-k:
                q.popleft()
            ans.append(nums[q[0]])
        return ans

复杂度： O(n)

liuguang520-lab commented 2 years ago

思路

采用分块进行处理，利用前缀和后缀

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //使用分块处理，利用前缀和后缀来表达一个区间的最大值。
        //初始化前缀
        vector<int> prefixmax(nums.size());
        for(int i = 0; i< nums.size(); i++)
        {
            if(i % k == 0)
            {
                prefixmax[i] = nums[i];//处于区间的开始
            }
            else
            {
                prefixmax[i] = max(prefixmax[i-1], nums[i]);
            }
        }
        vector<int> suffixmax(nums.size());
        for(int i = nums.size() - 1; i>= 0; i--)
        {
            if( i == nums.size() - 1 || (i+1) % k == 0)
            {
                suffixmax[i] = nums[i]; //处于区间末尾
            }
            else
            {
                suffixmax[i] = max(suffixmax[i+1], nums[i]);
            }
        }

        vector<int> ans;
        for(int i =0; i<= nums.size() - k ; i++)
        {
            ans.push_back(max(suffixmax[i], prefixmax[i + k - 1]));//交叉域就是所要求的
        }
        return ans;
    }
};

复杂度分析

时间复杂度o(n)
空间复杂度o(n)

JiangWenqi commented 2 years ago

维护一个单调递减的双端队列

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        vector<int> res;
        deque<int> dq;
        for (int i = 0; i < nums.size(); i++) {
            if (dq.size() && i - k == dq.front()) dq.pop_front();
            while (dq.size() && nums[i] > nums[dq.back()]) dq.pop_back();
            dq.push_back(i);
            if (i >= k - 1) res.push_back(nums[dq.front()]);
        }
        return res;
    }
};

O(n) O(n)

kite-fly6618 commented 2 years ago

思路：

双端队列 + 滑动窗口

代码：

 // 保持一个滑动窗口，内部递减，且是一个双端队列
var maxSlidingWindow = function (nums, k) {
    let res = []
    let len = nums.length
    let slidewindow = [] // 保存元素下标
    for (let i = 0;i < len;i++) {
        // 保证双端队列递减，每次取队列头
        while(slidewindow.length&&nums[i]>=nums[slidewindow[slidewindow.length-1]]) {
            slidewindow.pop()
        }
        slidewindow.push(i)
        // 当队列首部元素不在窗口中时，需要移除掉
        while(slidewindow[0]<=i-k) {
            slidewindow.shift()
        }
        if (i>=k-1) res.push(nums[slidewindow[0]])
    }
    return res
}

复杂度：

时间复杂度: O(n)
空间复杂度: O(n)

KennethAlgol commented 2 years ago

思路

双端队列


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;
    }
}

PFyyh commented 2 years ago

题目地址(239. 滑动窗口最大值)

https://leetcode-cn.com/problems/sliding-window-maximum/

题目描述

给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。

返回 滑动窗口中的最大值 。

 

示例 1：

输入：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

示例 2：

输入：nums = [1], k = 1
输出：[1]

 

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length

前置知识

单调栈

公司

暂无

思路

关键点

定义滑动窗口的大小的队列，队首是滑动窗口的最大元素。存值的时候，取出比自己小的元素，保持单调减。（看题解，大顶堆，又学了一手API妙用）

代码

语言支持：Java

Java Code:


class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        //结果
        int[] ans = new int[nums.length - k + 1];
        //定义队列，存储下标
        Deque<Integer> deque = new ArrayDeque<>();
        //开始遍历
        for (int i = 0; i < nums.length; i++){
            //获取队首的下标+窗口大小是否小于了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) ans[i - k + 1] = nums[deque.peekFirst()];
        }
        return ans;
    }
}

复杂度分析

令 n 为数组长度。k是滑动窗口大小

时间复杂度：$O(n)$
空间复杂度：$O(k)$

xiayuhui231 commented 2 years ago

题目

滑动窗口最大值 https://leetcode-cn.com/problems/sliding-window-maximum/comments/

思路

遇到一个新元素就把队列尾部不大于它的元素都弹出去，并且在尾部压入新元素如果队列头部元素超出窗口范围，就弹出头部每次头部元素是最大值，输出到结果中即可

代码

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
  vector<int> res;
        deque<int> a;
        for(int i=0;i<nums.size();i++){
            while(!a.empty()&&nums[a.back()]<=nums[i])
                a.pop_back();
            if(!a.empty()&&a.front()==i-k)
                a.pop_front();
            a.push_back(i);
            if(i>=k-1)
                res.push_back(nums[a.front()]);
        }
        return res;
    }
};

复杂度

时间复杂度：O(n) 空间复杂度：O(1)

zhishinaigai commented 2 years ago

思路

单调队列

代码

vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len=nums.size();
        deque<int> q;
        for(int i=0;i<k;i++){
            while(!q.empty()&&nums[i]>=nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
        }
        vector<int> ans {nums[q.front()]};
        for(int i=k;i<len;i++){
            while(!q.empty()&&nums[i]>=nums[q.back()]){
                q.pop_back();
            }
            q.push_back(i);
            while(q.front()<=i-k){
                q.pop_front();
            }
            ans.push_back(nums[q.front()]);
        }
        return ans;
    }

复杂度

时间：O(n) 空间：O(k)

miss1 commented 2 years ago

思路

建立一个递减的双端队列，存储窗口中的值。窗口移动时，入队的数小于等于队尾时直接入队，若大于队尾则一直出队直到数字不大于队尾。

（要寻找最大值，所以队尾小于当前数字的值都无价值，需要出队抛弃掉）。

左指针需要出队的失效元素，如果小于队头，根据入队规则说明之前已经被抛弃掉了，所以不做处理，等于队头的时候才要移除队头。

代码

var maxSlidingWindow = function(nums, k) {
  let queue = [nums[0]];
  for (let i = 1; i < k; i++) pushVal(nums[i], queue);
  let res = [queue[0]];
  let left = 0, right = k - 1;
  while (right + 1 < nums.length) {
    if (nums[left] >= queue[0]) queue.shift();
    pushVal(nums[right + 1], queue);
    res.push(queue[0]);
    left++;
    right++;
  }
  return res;
};

// 入队
let pushVal = function(val, queue) {
  if (val <= queue[queue.length - 1]) queue.push(val);
  else {
    while (queue[queue.length - 1] < val) queue.pop();
    queue.push(val);
  }
};

复杂度

time: O(n)

space: O(k)

Size-of commented 2 years ago

代码

语言支持：JavaScript

JavaScript Code:


var maxSlidingWindow = function(nums, k) {
    var left = 0
    var res = []
    for (var i = 0; i + k <= nums.length; i++) {
        findMaxNum(nums, left, k)
        left++
    }
    return res

    function findMaxNum(list, start, length) {
        var max =  -Infinity;
        for (var i = start; i < start + length; i++) {
            max = Math.max( list[i] , max)
        }
        res.push(max)
    }
};

复杂度分析

令 n 为数组长度。

时间复杂度：$O(n)$
空间复杂度：$O(1)$

LQyt2012 commented 2 years ago

思路

双向单调队列维护滑动中的序列大小顺序，队首就是滑动窗口的最大值。right指针移动时，判断right指针是否比队尾大，如果大则队尾出队。left指针移动时，判断left是否为当前窗口最大值，如果是，队首出队。

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        deque_index = collections.deque()
        left = 0
        right = 0
        length = len(nums)
        res = []
        while right < length:
            if right - left < k:
                while len(deque_index) != 0 and nums[deque_index[-1]] <= nums[right]:
                    deque_index.pop()
                deque_index.append(right)
                right += 1
            else:
                res.append(nums[deque_index[0]])
                while len(deque_index) != 0 and nums[deque_index[-1]] <= nums[right]:
                    deque_index.pop()
                deque_index.append(right)
                if left == deque_index[0]:
                    deque_index.popleft()
                left += 1
                right += 1
        res.append(nums[deque_index[0]])
        return res

func maxSlidingWindow(nums []int, k int) []int {
    left := 0
    right := 0
    length := len(nums)
    queueIndex := []int{}
    res := []int{}
    for right < length {
        if right - left < k {
            for len(queueIndex) != 0 && nums[queueIndex[len(queueIndex)-1]] <= nums[right] {
                queueIndex = queueIndex[:len(queueIndex)-1]
            }
            queueIndex = append(queueIndex, right)
            right++
        } else {
            res = append(res, nums[queueIndex[0]])
            for len(queueIndex) != 0 && nums[queueIndex[len(queueIndex)-1]] <= nums[right] {
                queueIndex = queueIndex[:len(queueIndex)-1]
            }
            queueIndex = append(queueIndex, right)
            if left == queueIndex[0] {
                queueIndex = queueIndex[1:]
            }
            left++
            right++
        }
    }
    res = append(res, nums[queueIndex[0]])
    return res
}

复杂度分析

时间复杂度：O(N)
空间复杂度：O(K)

forestie9 commented 2 years ago

Ideas

monotonic queue

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        n = len(nums)
        res = []
        q = deque()
        for i in range(n):
            while q and nums[q[-1]] < nums[i]: #q[-1] is popright (end of queue, min in queue)
                q.pop()
            q.append(i)
            if q[0] == i - k: ## 队头删除元素的index
                q.popleft()
            if i >= k - 1: ## 先把窗口的前 k - 1 填满, 就可以开始记录最大值了
                res.append(nums[q[0]])
        return res

O(N) time and space

mo660 commented 2 years ago

思路

双端递减队列+双指针

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        int len = nums.size();
        int slow = 0, fast = 0;
        deque<int>q;
        vector<int>res;
        while(fast < len){
            while((!q.empty()) && (nums[q.back()]<nums[fast])){
                q.pop_back();
            }
            q.push_back(fast);
            if (slow > q.front()){
                q.pop_front();
            }
            if (fast-slow+1 >= k){
                res.push_back(nums[q.front()]);
                slow++;
            }
            fast++;
        }
        return res;
    }
};

wychmod commented 2 years ago

思路

双端递减队列：假如一个新的数字进入窗口，当它大于的时候会弹出他前面小于的位置，当它小于的时候直接加入后面，这样在它前面因为出了窗口，这个相对较小的就变为最大的值。同时要保证队列里的数量不能超过k。

代码

class Solution:
    def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]:
        que = collections.deque() 
        ans = []
        for i in range(len(nums)):
            while que and nums[que[-1]] < nums[i]:
                que.pop()
            while que and i-que[0] >= k:
                que.popleft()
            que.append(i)
            if i+1>=k:
                ans.append(nums[que[0]])
        return ans

复杂度分析

时间复杂度On 空间复杂度Ok

AConcert commented 2 years ago

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;
};

KWDFW commented 2 years ago

Day28

239、滑动窗口最大值

javascript #队列

思路

1、创建一个单调递减的双端队列来保存接下来的滑动窗口中可能出现最大值的数

2、每次入队时，把比入队值小的数都移除，从队尾移除

3、每次右移一个，就把索引大于i-k+1的数移除，因为超出窗口的范围了

4、每次最大值取队列的队首即可

5、返回最大值数组

代码

var maxSlidingWindow = function(nums, k) {
    const res=[]//最终结果
    const dequeue=new Dequeue([])//初始化双端队列
    for(let i=0;i<k-1;i++){
        dequeue.push(nums[i])
    }//把前k-1个数入队
    for(i=k-1;i<nums.length;i++){
        dequeue.push(nums[i])//入队
        res.push(dequeue.max())//求最大值
        dequeue.shift(nums[i-k+1])//出队
    }//求最大值
    return res
};

class Dequeue{
    constructor(nums){
        this.list=nums
    }

    push(val){
        const nums=this.list
        while(nums[nums.length-1]<val){
            nums.pop()
        }//比输入值小的都退出队列,保持队列单调递减,队头元素是最大值
        nums.push(val)
    }

    shift(val){
        let nums=this.list
        if(nums[0]===val){
            //有可能上一个滑动窗口中左侧的数已经在push操作中被删除了,不能无脑删首元素
            nums.shift()
        }
    }
    //清除上一个滑动窗口中左侧的数

    max(){
        return this.list[0]
    }//返回队列的最大值
}

复杂度分析

时间复杂度：O(n)

空间复杂度：O(n)

leetcode-pp / 91alg-7-daily-check

【Day 28 】2022-04-28 - 239. 滑动窗口最大值 #31

239. 滑动窗口最大值

入选理由

题目地址

前置知识

题目描述

思路

代码

复杂度分析

思路

代码

复杂度

Idea

Code

Complexity

Idea

Code

Complexity:

思路

代码

复杂度

题目地址(239. 滑动窗口最大值)

题目描述

前置知识

思路

代码

思路

代码

复杂度分析

时间复杂度

空间复杂度

反思

代码

Day28 思路

复杂度分析

4.28

思路：

Idea

Code

代码

Idea

Code

Complexity

思路

题目

思路

代码

复杂度

239.滑动窗口最大值

题目链接

题目思路

题目的题解code

时间和空间复杂度

思路

代码

复杂度分析

思路

代码

复杂度分析

思路

代码

复杂度分析

思路

代码

复杂度

思路一：暴力求解

超时

单调递增队列

代码

复杂度

思路

代码

Idea

Code

Complexity

Code

Complexity

思路

复杂度分析