class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if(n==0||k==0) return nums;
        int[] res = new int[n - k + 1];

        //dq里存的是数组的index,不是数组的值
        Deque<Integer> dq = new LinkedList<>();

        for (int i = 0; i < n; i++) {

            //1.移除头部,保证窗口的长度范围
            if(!dq.isEmpty()&&dq.getFirst()<(i-k+1)){
                dq.removeFirst();
            }

            //2.移除尾部小于当前值的元素
            while (!dq.isEmpty()&&nums[i]>=nums[dq.getLast()]){
                dq.removeLast();
            }

            //3.尾部加入,滑动窗口向右扩充
            dq.addLast(i);

            //4.从头部返回最大值
            if(i>=k-1){
                res[i-k+1]=nums[dq.getFirst()];
            }
        }
        return res;
    }
}

总结维护单调双端队列的四个步骤:

(头,尾,尾,头)
第一步,头部出队
第二步,尾部清理
第三步,尾部入队
第四步,返回头部

Last modification:April 21st, 2020 at 01:09 pm