Nameless Site

But one day, you will stand before its decrepit gate,without really knowing why.

0%

滑动窗口中的最大值

Posted on In , ,
Symbols count in article: 2.5k Reading time ≈ 2 mins.

来源Leetcode第239题滑动窗口中的最大值

给定一个数组 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 ≤ 输入数组的大小。

暴力遍历

思路同重复元素III，在数组中划定长度为k的滑动窗口，通过2重循环，依次找到每个滑动窗口里的最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int[] maxSlidingWindow(int[] nums, int k) {
    int len = nums.length;
    if(len * k == 0)
        return new int[0];
    int [] ans = new int[len - k + 1];
    //LinkedList<Integer> queue = new LinkedList<>();
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < len - k + 1; i++){
        max = Integer.MIN_VALUE;
        for(int j = i; j < i + k; j++)
            max = Math.max(max,nums[j]);
        ans[i] = max;
    }
    return ans;
}

单调队列

来源

「单调队列」的核心思路和「单调栈」类似。单调队列的 push 方法依然在队尾添加元素，但是要把前面比新元素小的元素都删掉.

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
40
41
42
43
class deque{
    private LinkedList<Integer> data;

    public void push(int n){
        while(!data.isEmpty() && data.getLast() < n)
            data.removeLast();
        data.addLast(n);
    }

    public int max(){
        return data.getFirst();
    }

    public void pop(int n){
        if(!data.isEmpty() && data.getFirst() ==n)
            data.removeFirst();
    }

    public deque(){
        data = new LinkedList<>();
    }
}

public int[] maxSlidingWindow(int[] nums, int k) {
    int len = nums.length;
    if(len * k == 0)
        return new int[0];
    int [] ans = new int[len - k + 1];
    //LinkedList<Integer> queue = new LinkedList<>();
    deque window = new deque();
    for(int i = 0 ; i < nums.length; i++){
        if(i < k - 1)
            window.push(nums[i]);  //先填满窗口前的k - 1
        else
        {
            //窗口向前滑动
            window.push(nums[i]);
            ans[i - k + 1] = window.max();
            window.pop(nums[i-k+1]);
        }
    }
    return ans;
}

遍历

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
public int[] maxSlidingWindow(int[] nums, int k) {

    if(nums.length * k == 0){
        return new int[0];
    }

    int[] ans=new int[nums.length-k+1];
    if(nums.length<k){
        return new int[]{};
    }

    int begin=0;
    int end=k-1;
    int count=0;
    int max=Integer.MIN_VALUE;
    int stand=0;

    for(int i=0;i<=k-1;i++){  //先填充初始滑动窗口
        if(max<nums[i]){
            max=nums[i];
            stand=i; //记录最大值的位置
        }
    }

    ans[count]=nums[stand];
    count++;
    begin++;
    end++;
    
    while(end<nums.length){
        
        if(nums[end]>max){
            max=nums[end];
            stand=end;

        }
        
        if(begin>stand){  //最大值离开了滑动窗口
            max=Integer.MIN_VALUE;
            for(int i=begin;i<=end;i++){
                if(max<nums[i]){
                    max=nums[i];
                    stand=i;
                }
            }
        }
        
        ans[count]=nums[stand];
        count++;
        begin++;
        end++;

    }
    return ans;
}