2021-03-30极客时间打卡

剑指 Offer 59 - II. 队列的最大值https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]

public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        if(length == 0){
            return new int[0];
        }
        int max = Integer.MIN_VALUE;
        int maxInd = -1;
        int[] res = new int[length-k+1];
        for(int i =0;i<length-k+1;i++){
            if(maxInd >= i){
                if(max < nums[i+k-1]){
                    max = nums[i+k-1];
                    maxInd = i+k-1;
                }
            }else{
                max = nums[i];
                for(int j =i+1;j<i+k;j++){
                    if(max < nums[j]){
                        max = nums[j];
                        maxInd = j;
                    }
                }
            }
            res[i] = max;
        }
        return res;
    }

剑指 Offer 59 - I. 滑动窗口的最大值https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。
若队列为空，pop_front 和 max_value 需要返回 -1

输入:
["MaxQueue","push_back","push_back","max_value","pop_front","max_value"]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

Queue<Integer> queue;
        LinkedList<Integer> max;

        public MaxQueue() {
            queue = new LinkedList<>();
            max = new LinkedList<>();
        }

        public int max_value() {
            return max.size() == 0 ? -1 : max.getFirst();
        }

        public void push_back(int value) {
            queue.add(value);
            while (max.size() != 0 && max.getLast() < value) {
                max.removeLast();
            }
            max.add(value);
        }

        public int pop_front() {
            if (max.size() != 0 && queue.peek().equals(max.getFirst()))
                max.removeFirst();
            return queue.size() == 0 ? -1 : queue.poll();
        }