239-sliding-window-maximum.md

239. Sliding Window Maximum - 滑动窗口最大值

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

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

 

示例:

输入: 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 / Sliding Window

题目链接：LeetCode / LeetCode中国

题解

Language	Runtime	Memory
java	7 ms	42.9 MB

class Solution {
    class Node {
        int index;
        int value;
        Node(int index, int value) {
            this.index = index;
            this.value = value;
        }
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k == 0 || nums.length == 0) return new int[0];
        LinkedList<Node> list = new LinkedList<>();
        int[] ans = new int[nums.length];
        for (int i = 0; i < nums.length; i++) {
            while (!list.isEmpty() && list.getLast().value <= nums[i]) {
                list.removeLast();
            }
            while (!list.isEmpty() && i - list.getFirst().index >= k) {
                list.removeFirst();
            }
            list.addLast(new Node(i, nums[i]));
            ans[i] = list.getFirst().value;
        }
        return Arrays.copyOfRange(ans, k - 1, ans.length);
    }
}