【解题报告】【lintcode362】Sliding Window Maximum

题意

给出一组数字，一个滑动窗口的大小，窗口从开始滑动到数字结束，返回每次窗口中的最大值

解答

由于时间复杂度的要求，我们不能暴力求解，因为这样的复杂度是n*n级别，而题目要求n级别 我们可以通过记录数组下标来解答这个题目 每次新的数字进入时，把小于它的数字下标全部移除，形成递减的结果数组，每次取这个数组的第一个就是当前窗口最大的数了 由于每一个数字只会被操作两次，一次是进入，一次是弹出，所以时间复杂度是O(n)的

代码

public class SlidingWindowMaximum {
    public ArrayList<Integer> maxSlidingWindow(int[] nums, int k) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        LinkedList<Integer> deque = new LinkedList<Integer>();
        int[] res = new int[nums.length + 1 - k];
        for (int i = 0; i < nums.length; i++) {
            if (!deque.isEmpty() && deque.peekFirst() == i - k)
                deque.poll();
            while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i])
                deque.removeLast();
            deque.offerLast(i);
            if ((i + 1) >= k) res[i + 1 - k] = nums[deque.peek()];
        }
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 0; i < res.length; i++) {
            list.add(res[i]);
        }
        return list;
    }
}