leetcode-sliding-window-maximum

发表于   |   分类于 ，   |  

题目大意

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

　　给你一个数组nums和窗口大小k，窗口最开始左边界位于0的位置，之后每次右移一位，输出每个窗口内元素的最大值。

题目分析

　　暴力方法O(n*k)可解，如果利用堆可以O(n * logk)，但题目要求了复杂度是O(n)，也就是和k无关的，我参考了discuss区的这篇解法:https://discuss.leetcode.com/topic/19067/clean-c-o-n-solution-using-a-deque 思路还是比较容易理解，利用双端队列（模拟窗口）维护一个递减序列，序列的头部就是窗口最大值，当然要注意如果元素个数超出窗口大小k，就要移除头部元素。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        ArrayDeque<Integer> dq = new ArrayDeque<Integer>();
        List<Integer> ans = new ArrayList<Integer>();
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
                dq.pollLast();
            }
            dq.offerLast(i);
            if (dq.peekFirst() == (i - k)) {
                dq.pollFirst();
            }
            if (i >= k - 1) {
                ans.add(dq.peekFirst());
            }
        }
        int[] ans2 = new int[ans.size()];
        for (int i = 0; i < ans.size(); i++) {
            ans2[i] = nums[ans.get(i)];
        }
        return ans2;
    }
}