239. 滑动窗口最大值

题目描述

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

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

解题思路

这里我们可以自己设计个队列，这个队列里面主体数据结构我们使用Java里的Deque这个双向队列，我们向这个队列里放入元素的时候我们的原则是只维持队列里面最大的元素在我们这个双向队列的头部位置，当我们的滑动窗口向后滑动的时候，如果此时我们要弹出的元素不是队列的头部元素我们就直接跳过(说明在此前添加进来的时候就被pass掉了)，如果我们此时要弹出的元素是队列的头部元素，我们就要把头部元素弹出，然后向后依次遍历就可以了，主体思路就是我们只维持最大的元素在我们队列的头部就行了

import java.util.*;

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 1) {
            return nums;
        }
        List<Integer> result = new ArrayList<>();

        MyQueue queue = new MyQueue();

        for (int i = 0; i < k; i++) {
            queue.push(nums[i]);
        }
        result.add(queue.getMax());

        for (int j = k; j < nums.length; j++) {
            queue.pop(nums[j - k]);
            queue.push(nums[j]);
            result.add(queue.getMax());
        }

        int[] num = result.stream().mapToInt(Integer::intValue).toArray();
        return num;

    }

    class MyQueue {
        Deque<Integer> deque = new LinkedList<>();

        public void pop(int value) {
            if (!deque.isEmpty() && deque.getFirst() == value) {
                deque.pollFirst();
            }
        }
        
        public void push(int value) {
            while (!deque.isEmpty() && deque.getLast() < value) {
                deque.pollLast();
            }
            deque.addLast(value);
        }

        public int getMax() {
            return deque.getFirst();
        }

    }

}