Short Java using Deque but not storing index. 中文版.


  • 0
    B

    我这个答案的deque里存的直接是数值。当window左端将要被移出的那个元素大小等于目前最大值的时候,我们就把目前最大值,也就是Deque的顶部元素移出。不过也可能存index更加直观。
    这题的精髓感觉就是要发现:如果新加入的元素比之前的一些大的话,之前那些大的都是废的.有些用stack的题其实也是这样的操作。这题由于window左边也需要向右移动,移除元素,所以使用了Deque,倘若window左边固定,可以用stack解(其实只要存一个max就好,不用stack)。
    希望对大家理解有用.
    Here we do not store index but value of the array in Deque. Hope it helps.

        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums == null || nums.length == 0 || k < 1 || k > nums.length) return new int[0];
            
            Deque<Integer> deq = new ArrayDeque<>();
            int[] res = new int[nums.length-k+1];
            
            for (int i = 0; i < nums.length; i++) {
                while (!deq.isEmpty() && deq.peekLast() < nums[i]) 
                    deq.pollLast();//对于即将加入deque的新元素,删除之前比他小的,注意这里必须要用<而不是<=。
                deq.offerLast(nums[i]);
                
                if (i >= k-1) res[i-k+1] = deq.peekFirst();
                if (i >= k-1 && nums[i-k+1] == deq.peekFirst()) deq.pollFirst();//如果左边指针指向的值真好是目前的最大值,则删除最大值,为下一个循环做准备。高票答案好像是用一个while先做去除的,可能那样更加直观。
            }
            
            return res;
        }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.