Very easy to understand, Java O(n) LinkedList solution, Beat 92%


  • 0
    W
    public class Solution {
        // Insert
        private void maxDequeInsert(LinkedList<Integer> d, int x)
        {
            if (d.isEmpty())
                d.addLast(x);
            else
            {
                while (!d.isEmpty() && d.getLast()<x)
                    d.removeLast();
                d.addLast(x);
            }
        }
        // Remove
        private void maxDequeRemove(LinkedList<Integer> d, int x)
        {
            if (x == d.getFirst())
                d.removeFirst();
        }
        // getMax
        private int maxValue(LinkedList<Integer> d)
        {
            return d.getFirst();
        }
        
        
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0)
                return new int[0];
            
            int[] ret = new int[nums.length + 1 - k];
            
            LinkedList<Integer> d = new LinkedList<>();
            for (int i=0; i<k; i++)
            {
                maxDequeInsert(d, nums[i]);
            }
            ret[0] = maxValue(d);
            for (int i=1; i<=nums.length - k; i++)
            {
                int rev = nums[i-1];
                int ins = nums[i+k-1];
                
                maxDequeRemove(d, rev);
                maxDequeInsert(d, ins);
                ret[i] = maxValue(d);
            }
            
            return ret;
        }
    }
    

  • 1
    U

    Great solution! thanks.

    I took the freedom to modify your code. In this way you can do everything in one pass.

    public class Solution {
        // Insert
        private void maxDequeInsert(LinkedList<Integer> d, int x)
        {
            if (d.isEmpty())
                d.addLast(x);
            else
            {
                while (!d.isEmpty() && d.getLast()<x)
                    d.removeLast();
                d.addLast(x);
            }
        }
        // Remove
        private void maxDequeRemove(LinkedList<Integer> d, int x)
        {
            if (x == d.getFirst())
                d.removeFirst();
        }
        // getMax
        private int maxValue(LinkedList<Integer> d)
        {
            return d.getFirst();
        }
        
        
        public int[] maxSlidingWindow(int[] nums, int k) {
            if (nums.length == 0)
                return new int[0];
            
            int[] ret = new int[nums.length + 1 - k];
            
            LinkedList<Integer> d = new LinkedList<>();
            for (int i=0; i<nums.length; i++)
            {
                maxDequeInsert(d, nums[i]);
                if(i >= k)
                    maxDequeRemove(d,nums[i-k]);
                if(i >= k-1)
                    ret[i-k+1] = maxValue(d);
            }
            return ret;
        }
    }
    

Log in to reply
 

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