Leetcode sword finger offer question brushing - day 27

Leetcode The finger of the sword Offer How to brush questions ：

Leetcode The finger of the sword Offer Brush problem - Learning plan directory _DEGv587 The blog of -CSDN Blog

The finger of the sword Offer 59 - I. Maximum sliding window

Solution 1 ： Violent simulation

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int len = nums.length - k + 1;
        List<Integer> list = new ArrayList<>();
        int[] ret = new int[len];
        
        for (int i = 0; i < len; ++i) {
            int max = Integer.MIN_VALUE;
            for (int j = i; j < i + k; ++j) {
                max = Math.max(nums[j], max);
            }
            list.add(max);
        }
        for (int i = 0; i < len; ++i) {
            ret[i] = list.get(i);
        }
        return ret;
    }
}

Solution 2 ： A monotonous queue （ Optimized version ）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0 || k == 0) return new int[0];
        Deque<Integer> deque = new LinkedList<>();
        int[] ret = new int[nums.length - k + 1];
        int index = 0;
        // No window interval is formed 
        for (int i = 0; i < k; ++i) {
            // When the queue is not empty , Compare the current value with the value at the end of the queue , If it is greater than , Delete the value at the end of the queue 
            // The value in the queue is greater than the current value until the circular deletion , Or delete to a queue that is empty 
            while (!deque.isEmpty() && nums[i] > deque.peekLast()) {
                deque.removeLast();
            }
            // After executing the above loop , The queue is either empty , Either the value is greater than the current value , Then add the current value to the queue 
            deque.addLast(nums[i]);
        }

        // Just after the window is formed , Add the first value of the queue to the queue 
        ret[index++] = deque.peekFirst();

        // Window sections form 
        for (int i = k; i < nums.length; ++i) {
            //i-k It's already outside the range , If the first is equal to nums[i-k], Then it means that the first value is no longer in the range , You need to remove 
            if (deque.peekFirst() == nums[i - k]) {
                deque.removeFirst();
            }
            // Delete the value in the queue that is smaller than the current value 
            while (!deque.isEmpty() && deque.peekLast() < nums[i]) {
                deque.removeLast();
            }
            // Add the current value to the queue 
            deque.addLast(nums[i]);
            // Add the first value of the queue to arr Array 
            ret[index++] = deque.peekFirst();
        }

        return ret;
    }
}

The finger of the sword Offer 59 - II. The maximum value of the queue

solution ： The sliding window （ deque ）

class MaxQueue {
    Deque<Integer> queue, deque;

    public MaxQueue() {
        // Initialize queue  queue , The bidirectional queue  deque
        queue = new LinkedList<Integer>();
        deque = new LinkedList<Integer>();
    }

    public int max_value() {
        // When a two-way queue  deque  It's empty , Then return to  -1 ;
        // otherwise , return  deque  First element ;
        return deque.isEmpty() ? -1 : deque.peekFirst();
    }

    public void push_back(int value) {
        // Put the element  value  The team  queue ;
        queue.addLast(value);
        // End the queue in a two-way queue   all   Less than  value  Element pop-up （ To maintain  deque  Nonmonotonic decreasing ）, And put the elements  value  The team  deque
        while (!deque.isEmpty() && deque.peekLast() < value) {
            deque.removeLast();
        }
        deque.addLast(value);
    }

    public int pop_front() {
        // If queue  queue  It's empty , Then return directly  -1 ;
        if (queue.isEmpty()) return -1;
        // otherwise , take  queue  The first element is out of the team ;
        // if  deque  First element and  queue  First element   equal  , Will  deque  The first element is out of the team （ To keep two lines   The elements are the same  ） ;
        if (queue.peekFirst().equals(deque.peekFirst())) {
            deque.removeFirst();
        }
        return queue.removeFirst();
    }
}