代码随想录算法训练营DAY13 | 栈与队列 (3)

一、LeetCode 239 滑动窗口最大值

题目链接：239.滑动窗口最大值https://leetcode.cn/problems/sliding-window-maximum/

思路：使用单调队列，只保存窗口中可能存在的最大值，从而降低时间复杂度。

public class MyQueue{
    Deque<Integer> queue = new LinkedList<>();
    //弹出元素时，判断要窗口弹出的数值是否等于队列出口的数值
    void poll(int val){
        if(!queue.isEmpty() && val == queue.peek()){
            queue.poll();
        }
    }
    //添加元素时，判断要添加的元素是否大于队列入口处的元素
    //如果大于，就将入口处元素弹出，保证队列单调递减
    void offer(int val){
        while(!queue.isEmpty() && val > queue.getLast()){
            queue.removeLast();
        }
        queue.offer(val);
    }
    //栈顶始终为最大值
    int peek(){
        return queue.peek();
    }
}
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 1){
            return nums;
        }
        int len = nums.length - k + 1;
        int[] ans = new int[len];
        int index = 0;
        MyQueue queue = new MyQueue();
        //先把前k个元素入队
        for(int i = 0; i < k; i++){
            queue.offer(nums[i]);
        }
        //记录前k个元素中的最大值
        ans[index++] = queue.peek();

        for(int i = k; i < nums.length; i++){
            //弹出 + 入队
            queue.poll(nums[i-k]);
            queue.offer(nums[i]);
            //记录每组窗口的最大值
            ans[index++] = queue.peek();
        }

        return ans;
    }
}

 二、LeetCode 347 前k个高频元素

        暂不更新