advancing9

发表于 分类于 ，

题目描述[题目描述][https://leetcode-cn.com/problems/sliding-window-maximum/]

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

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

示例:

1
2
3
4
5
6
7
8
9
10
11
12
输入: 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

提示：

你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

进阶：

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

算法描述

如何优化时间复杂度呢？首先想到的是使用堆，因为在最大堆中 heap[0] 永远是最大的元素。在大小为 k 的堆中插入一个元素消耗 log(k) 时间，因此算法的时间复杂度为 O(Nlog(k))。

能否得到只要 {O}(N)O(N) 的算法？

我们可以使用双向队列，该数据结构可以从两端以常数时间压入/弹出元素。

存储双向队列的索引比存储元素更方便，因为两者都能在数组解析中使用。

算法

算法非常直截了当：

  • 处理前 k 个元素，初始化双向队列。

  • 遍历整个数组。在每一步 :

    清理双向队列 :

    1
    2
    3
    - 只保留当前滑动窗口中有的元素的索引。
      
    - 移除比当前元素小的所有元素，它们不可能是最大的。

  • 将当前元素添加到双向队列中。

  • 将 deque[0] 添加到输出中。

  • 返回输出数组。

C++代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
         int n = nums.size();
        vector<int> ans;
        deque<int> q;
        for(int i=0;i<n;i++){
            while(!q.empty()&&i-q.front()>=k)
                q.pop_front();
            while(!q.empty()&&nums[i]>=nums[q.back()])
                q.pop_back();
            q.push_back(i);
            if(i>=k-1)
                ans.push_back(nums[q.front()]);
        }
        return ans;
    }
};

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
  ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
  int [] nums;

  public void clean_deque(int i, int k) {

    if (!deq.isEmpty() && deq.getFirst() == i - k)
      deq.removeFirst();

    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;

    this.nums = nums;
    int max_idx = 0;
    for (int i = 0; i < k; i++) {
      clean_deque(i, k);
      deq.addLast(i);

      if (nums[i] > nums[max_idx]) max_idx = i;
    }
    int [] output = new int[n - k + 1];
    output[0] = nums[max_idx];

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