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

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

单调队列
在增删元素的过程中要求能返回当前最大元素，和 155. 最小栈 类似。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length, p = 0;
        int[] res = new int[n - k + 1];
        MyQueue queue = new MyQueue();

        for(int i = 0; i < k - 1; i++) queue.offer(nums[i]);
        for(int i = k - 1; i < n; i++){
            queue.offer(nums[i]);
            res[p++] = queue.getMax();
            queue.poll(nums[i - k + 1]);
        }

        return res;
    }
}

class MyQueue{
    Deque<Integer> q_max = new ArrayDeque<>();;

    public void offer(int x){
        while(!q_max.isEmpty() && q_max.peekLast() < x){
            q_max.pollLast();
        }
        q_max.offerLast(x);
    }

    public void poll(int x){
        if(x == q_max.peekFirst()){
            q_max.pollFirst();
        }
    }

    public int getMax(){
        return q_max.peekFirst();
    }
}

结果用 List 转为数组，不用计算元素个数。

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        List<Integer> res = new ArrayList<>();
        MyQueue queue = new MyQueue();

        for(int i = 0; i < k - 1; i++) queue.offer(nums[i]);
        for(int i = k - 1; i < n; i++){
            queue.offer(nums[i]);
            res.add(queue.getMax());
            queue.poll(nums[i - k + 1]);
        }

        return res.stream().mapToInt(x -> x).toArray();
    }
}