Java O(n) deque solution with my thinking process


  • 0
    L

    To solution the problem, we care about two things.

    1. The max value in the current window.
    2. If the window moves, max value might go out of window, then what is the max value of the new window?

    We hope to find out the answer to the above two questions instantly as we move the window.

    This reminds me of the Min-Stack Problem. One of the solution to that problem is whenever we push a bigger value, say A, to the stack, we put a dummy value, which is the biggest value before, say B, under A. Then when we pop A out of stack, we instantly know that B is the biggest value of the rest for the stack.

    For this question, we use a deque (double-ended queue) because we want to do some operations from both side of the queue. We keep the biggest value at the bottom of the queue, and keep pushing element smaller to the queue. Before we push a new value A, we compare it with the peek value B in the queue, and if the B < A, we pop B out and keep the comparison until finally A>=B, then we push A to the peek of queue. So at anytime in the queue, the values are always in a descending order (from bottom to top).

    When we move the window, we also care about when the current max value go out of window. The strategy here is: If the start element of the window is the same as the bottom value of queue, then we know that the current maximum value will not be in the window in the next move, so we pop it out. Then the next element in the queue automatically becomes the biggest value of next window.

    public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums == null || nums.length == 0) return new int[0];
            int n = nums.length;
            Deque<Integer> stack = new ArrayDeque();
            int[] rlt = new int[n-k+1];
            int index = 0, s = 0, e = 0;     // s is start index of window, e is end index 
            while(e<k-1){
                while(!stack.isEmpty() && nums[e] > stack.peek()) stack.pop();
                stack.push(nums[e]);
                e++;
            }
            while(e<nums.length){
                while(!stack.isEmpty() && nums[e] > stack.peek()) stack.pop();
                stack.push(nums[e]);
                rlt[index++] = stack.getLast();
                if(stack.getLast() == nums[s]) stack.removeLast();
                e++; s++;
            }
            return rlt;
        }
    

  • 0
    M

    why not just update two variable to record max and secondMax? if max is out of the range, we will compare secondMax and the one getting in now.


Log in to reply
 

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