Short java O(n) solution just using LinkedList


  • 4
    L

    The idea is that we only maintain a descending list for window. Each time we add a element, we remove all the elements smaller that it since they would never influence the MAX. So the 1st element in the arraylist is always the maximum. When we move window one step right, if the left most element is not the MAX, do nothing, otherwise delete the 1st element in the descending list. In total the descending list would add and delete elements for N times, so this algorithm is amortized linear.

    //for function addDescList(). since we need to add element before delete it, in total we could only add and
    //delete for nums.length times at most. So it's linear time.

    public class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0) return new int[0];
            LinkedList<Integer> descList = new LinkedList<Integer>();
            int[] res = new int[nums.length+1-k];
            for(int i=0;i<k-1;i++) addDescList(descList,nums[i]);
            for(int i=0;i<res.length;i++){
                addDescList(descList,nums[i+k-1]);
                res[i] = descList.getFirst();
                if(nums[i]==descList.getFirst()) descList.removeFirst(); //to delete the left most.
            }
            return res;   
        }
        public void addDescList(List<Integer> descList, int num){
            while(!descList.isEmpty()&&num>descList.getLast()) descList.removeLast();
            descList.add(num);
        }  
    }

Log in to reply
 

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