Java O(n) solution with two stacks.


  • 6
    A

    The idea of the solution is to maintain two stacks: s1 and s2. We hope s1's peek is always to keep the largest value in the current k numbers. So we use s1 to store the numbers whose index is in increasing order and values is in decreasing order. For example give k=4 numbers 1, 3 ,9, 6. s1 only need to store 9 and 6 with 9 is on the peek of the stack.

    When we slide the window, we need to keep dumping the numbers at the left end of the window and adding new numbers on the right end of the window. When we have a new number in the window, we push just the new number in stack s2. Also, we keep record the largest value in s2. If the peek of s1 is smaller than the largest value in s2, it means the largest value in the current k numbers is in s2. Thus, we need to empty s1 and move the elements stored in s2 to s1. Note that we do not need to move all the elements in s2 to s1. Only the numbers whose index is in increasing order and values is in decreasing order are pushed into s1.

    For example,
    1,3,9,6,7,1, 2 , 5 given k=4

    step 1: window 1,3,9,6 s1: 9, 6 s2:empty maxInStack2=Integer.MIN_VALUE;

    step 2: window 3,9,6,7 s1: 9,6 s2:7 maxInStack2=7

    step3: window 9,6,7,1 s1: 9, 6 s2:7,1 maxInStack2=7

    step4: window 6,7,1, 2 note 9 is removed from window, so s1: 6 s2: 7, 1 ,2 maxInStack2=7
    Then we find that maxInStack2> s1.peek(). update s1.
    After updating s1, we have s1: 7, 2 s2: empty maxInStack2=Integer.MIN_VALUE;

    step5: window 7,1,2,5 s1:7,2 s2:5, maxInStack2=5;
    In worst case, every number in the array is visited twice. Thus the complexity is O(n)

    public class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums==null||nums.length==0) return nums;
        int [] result= new int[nums.length-k+1];
        int maxInStack2=Integer.MIN_VALUE;
        Stack<Integer> s1 =new Stack<Integer>();
        Stack<Integer> s2 =new Stack<Integer>();
        for(int i=k-1;i>=0;i--){
            if(s1.isEmpty()){
                s1.push(nums[i]);
            }else if(nums[i]>=s1.peek()){
                s1.push(nums[i]);
            }
        }
        result[0]=s1.peek();
        for(int i=1;i<result.length;i++){
            int newItem=nums[i+k-1];
            int removeItem=nums[i-1];
            if(removeItem==s1.peek()){
                s1.pop();
            }
            if(newItem>maxInStack2){
                maxInStack2=newItem;
            }
            s2.push(newItem);
            if(s1.isEmpty()||maxInStack2>s1.peek()){
                while(s1.isEmpty()==false){
                    s1.pop();
                }
                while(s2.isEmpty()==false){
                    int temp=s2.pop();
                    if(s1.isEmpty()||temp>=s1.peek()){
                        s1.push(temp);
                    }
                }
                result[i]=maxInStack2;
                maxInStack2=Integer.MIN_VALUE;
            }else{
                result[i]=s1.peek();
            }
        }
        return result;
    }
    

    }


Log in to reply
 

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