leetcode239. 滑动窗口最大值(java详解)

class Solution {
    


    public int[] maxSlidingWindow(int[] nums, int k) {
        
        if (nums.length == 1) return nums;

        MyQueue queue = new MyQueue();

        int len = nums.length - k + 1;//代数求出
        int[] ans = new int[len];
        int index = 0;

        for (int i = 0; i < k; i++) {
            queue.add(nums[i]);
        }

        ans[index++] = queue.peek();

        for (int i = k; i < nums.length; i++) {
            //移除队列 首个元素 可能最大值就是首部元素，也可能不是
            queue.poll(nums[i-k]);
            //添加新元素
            queue.add(nums[i]);
            ans[index++] = queue.peek();
        }


        return ans;
    }
}


class MyQueue{

    Deque deque = new LinkedList<>();
    
    //poll元素的的话,当前的这个数组是否为空,还有的就是当前队首元素是否为该窗口的最大值，如果是就移除
    //如果不是最大值的话,那么该滑动窗口中的元素的个数是不够k个的（因为我只是记录元素的相对位置）
    public void poll(int val) {
        if (!deque.isEmpty() && deque.peek() == val) {//队首元素
            deque.poll();
        }
    } 

    //在队尾添加元素
    //得判断队列中的尾部元素 tail 跟我们的要插入的值 insert 大小关系
    // tail < insert 那么的话 我们就移除队列尾部元素
    // tail > insert 那么的话 我们就正常添加
    public void add(int val) {
        while (!deque.isEmpty() && val > deque.getLast()) {//比队尾元素大的话
            deque.removeLast();
        }   
        deque.add(val);//比队尾元素小的话
    }

    //访问首部元素
    public int peek() {        
        return deque.peek();
    }


}

class Solution {
    

    public int max(int[] segment,int n) {
        int maxx = -999999;
        for (int i = 0; i < n; i++) {
            if (maxx < segment[i]) {
                maxx = segment[i];
            }
        }
        return maxx;
    }

    public int[] maxSlidingWindow(int[] nums, int k) {
        
        int len = nums.length-k+1;//代数求解
        int[] ans = new int[len];
        int ansIndex = 0;

        for (int i = 0; i < len; i++) {
            int[] temp = new int[k];
            int tempIndex = 0;
            int count = 0;
            int j = i;

            while (count != k) {
                temp[tempIndex++] = nums[j++];
                count++;
            }

            int eachAns = max(temp,k);
            ans[ansIndex++] = eachAns;
        }

        return ans;

    }
}