Leetcode - Sword finger offer 59 - I, 59 - II

The finger of the sword Offer 59 - I. Maximum sliding window 、59 - II. The maximum value of the queue

Title Description ：
[59 - I]
Given an array nums And the size of the sliding window k, Please find the maximum value in all sliding windows .
[59 - II]
Please define a queue and implement the function max_value Get the maximum in the queue , Function required max_value、push_back and pop_front The average time complexity of is O(1).

If the queue is empty ,pop_front and max_value Need to return -1

Key points of investigation ：
The first 59 - I topic Use priority queues ( Pile up ) Realize the sorting of elements in the window , Loop through the simulation window sliding
The first 59 - II topic Use a monotonic queue for assistance , Save the size relationship of queue elements .

The first 59 - I topic

     class Num{
    
        int pos;
        int val;
        public Num(int pos, int val){
    
            this.pos = pos;
            this.val = val;
        }
    }
    public int[] maxSlidingWindow(int[] nums, int k) {
    
        int[] res = new int[nums.length - k + 1];
        int recPos = 0;
        int left = 0, right = 0;
        int nLen = nums.length;
        if(nLen == 0){
    
            return new int[]{
    };
        }
        PriorityQueue<Num> pq = new PriorityQueue<>(new Comparator<Num>() {
    
            @Override
            public int compare(Num o1, Num o2) {
    
                if(o1.val > o2.val){
    
                    return -1;
                }else{
    
                    return 1;
                }
            }
        });

        while(right < nLen){
    
            Num num = new Num(right, nums[right]);
            pq.add(num);
            if(right - left >= k){
    
                for(Num p : pq){
    
                    if(p.pos == left){
    
                        pq.remove(p);
                        left ++;
                        break;
                    }
                }
            }
            if(right - left == k - 1)
                res[recPos++] = pq.peek().val;
            right ++;
        }
        return res;
    }

The first 59 - II topic

class MaxQueue {
    
    public Deque<Integer> que;
    public Deque<Integer> help;

    public MaxQueue() {
    
        que = new ArrayDeque<>();
        help = new ArrayDeque<>();
    }

    public int max_value() {
    
        if(que.size() == 0)
            return -1;
        int val = help.getFirst();
        return val;
    }

    public void push_back(int value) {
    
        que.addLast(value);
        while(help.size() != 0 && value > help.getLast()){
      // help It's a monotonous queue , When each element enters the team , Will kick out the inner elements smaller than it in front , In order to ensure that the queue is always monotonically decreasing 
            help.removeLast();
        }
        help.addLast(value);
    }

    public int pop_front() {
    
        if(que.size() == 0)
            return -1;
        int val = que.removeFirst();
        if(help.getFirst() == val) {
            //  First in, first out , So we just need to compare the out of team elements help Team leader element is enough 
            help.removeFirst();
        }
        return val;
    }
}

/** * Your MaxQueue object will be instantiated and called as such: * MaxQueue obj = new MaxQueue(); * int param_1 = obj.max_value(); * obj.push_back(value); * int param_3 = obj.pop_front(); */