剑指 Offer 59 - I. 滑动窗口的最大值

  • 时间复杂度O(n)
  • 单调栈，每次保证栈顶是最大值，不在滑动窗口中的元素删除
public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) {
            return new int[]{};
        }
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> deque = new LinkedList<>();
        int left = 0;
        for (int i = 0; i < nums.length; i++) {
            while (!deque.isEmpty() && nums[i] > nums[deque.peekLast()]) {
                deque.removeLast();
            }
            deque.addLast(i);

            if (deque.peekFirst() <= i - k) {
                deque.removeFirst();
            }

            if (i + 1 >= k) {
                result[left] = nums[deque.peekFirst()];
                left++;
            }
        }
        return result;
    }