算法60天训练–9-18-day13

思路

因为要求滑动窗口中的最大值, 所以比较容易实现的便是,自己定义一个结构,能够让队列头始终是滑动窗口中最大的:

Code

Java

class MyQue{
    Deque<Integer> deque = new LinkedList<>();
    void poll(int value){
        if(!deque.isEmpty() && value == deque.peek()){
            deque.poll();
        }
    }
        void add(int val){
            while(!deque.isEmpty()  && val > deque.getLast()){
                deque.removeLast();
            }
            deque.add(val);
        }

        int peek(){
            return deque.peek();
        }
    
}
class Solution {

    
    public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length == 1){
        return nums;
    }
    int len = nums.length - k  + 1;
    // 存放结果元素的数组
    int[] res = new int[len];
    int num = 0;

    MyQue myque = new MyQue();

    for(int i = 0; i < k; i++){
        myque.add(nums[i]);
    }
    res[num++] = myque.peek();
    for(int i = k; i < nums.length; i++){
        myque.poll(nums[i-k]);

        myque.add(nums[i]);
        res[num++] = myque.peek();
    }

    return res;
    }

}

C++

class MyQue{
    Deque<Integer> deque = new LinkedList<>();
    void poll(int value){
        if(!deque.isEmpty() && value == deque.peek()){
            deque.poll();
        }
    }
        void add(int val){
            while(!deque.isEmpty()  && val > deque.getLast()){
                deque.removeLast();
            }
            deque.add(val);
        }

        int peek(){
            return deque.peek();
        }
    
}
class Solution {

    
    public int[] maxSlidingWindow(int[] nums, int k) {
    if(nums.length == 1){
        return nums;
    }
    int len = nums.length - k  + 1;
    // 存放结果元素的数组
    int[] res = new int[len];
    int num = 0;

    MyQue myque = new MyQue();

    for(int i = 0; i < k; i++){
        myque.add(nums[i]);
    }
    res[num++] = myque.peek();
    for(int i = k; i < nums.length; i++){
        myque.poll(nums[i-k]);

        myque.add(nums[i]);
        res[num++] = myque.peek();
    }

    return res;
    }

}