题目

leetcode 239 有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

1
2
3
4
5
6
7
8
例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时:
[4 3 5] 4 3 3 6 7
4 [3 5 4] 3 3 6 7
4 3 [5 4 3] 3 6 7
4 3 5 [4 3 3] 6 7
4 3 5 4 [3 3 6] 7
4 3 5 4 3 [3 6 7]
窗口中最大值为5，窗口中最大值为5 ，窗口中最大值为5，窗口中最大值为4，窗口中最大值为6，窗口中最大值为7

如果数组长度为n，窗口大小为w，则一共产生n-w+1个窗口的最大值。

请实现一个函数。输入:整型数组arr，窗口大小为w。
输出:一个长度为n-w+1的数组res，res[i]表示每一种窗口状态下的以本题为例，结果应该为[5,5,5,4,6,7]

滑动窗口

滑动窗口就是一个动态的窗口，这个窗口可以是固定长度，也可以是可变长度。使用双端队列实现滑动窗口这种数据结构，滑动窗口从头部到尾部由大到小。

双端队列维持的是什么信息？如果目前的R不在扩大，让L依次移动1个位置，得到每个位置时窗口的最大值。

什么情况可以用滑动窗口来解决实际问题呢？

  1. 一般给出的数据结构是数组或者字符串
  2. 求取某个子串或者子序列最长最短等最值问题或者求某个目标值时
  3. 该问题本身可以通过暴力求解

时间复杂度：窗口划过数字时，每个位置的数最多进窗口一次，最多出窗口一次。O(n)

代码

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
37
38
39
public class MaxSlidingWindow {

    public int[] maxSlidingWindow(int[] nums, int k) {
        //双端队列
        LinkedList<Integer> deque = new LinkedList<>();
        List<Integer> result = new ArrayList<>();
        int L = 0;
        int R = 0;

        for (int i = 0; i < nums.length; i++) {

            // 保持双端队列结构， 从大到小
            while (deque.size() > 0 && nums[deque.getLast()] < nums[i]) {
                deque.removeLast();
            }
            deque.add(i);

            if (R - L + 1 == k) { // 达到窗口的值时添加最大值
                result.add(nums[deque.getFirst()]);
                if (nums[deque.getFirst()] == nums[L]) { //出栈
                    deque.removeFirst();
                }
                L++;
            }
            R++;

        }
        return result.stream().mapToInt(Integer::intValue).toArray();
    }

    public static void main(String[] args) {
        MaxSlidingWindow maxSlidingWindow = new MaxSlidingWindow();

        /*int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        System.out.println(Arrays.toString(maxSlidingWindow.maxSlidingWindow(nums, 3)));*/
        int[] nums = {1};
        System.out.println(Arrays.toString(maxSlidingWindow.maxSlidingWindow(nums, 1)));
    }
}