O(n) Java solution


  • -1
    W

    the code is quite self explaining.

     class Lst {
        public final int size;
        private final int[] array;
        private int head, tail;
    
        Lst(int size) {
            this.size = size;
            this.array = new int[size];
            this.head = 0;
            this.tail = -1;
        }
    
        public int first() {
            return array[head];
        }
    
        public int popFirst() {
            return array[head++];
        }
    
        public void append(int t) {
            array[++tail] = t;
        }
    
        public int last() {
            return array[tail];
        }
    
        public int popLast() {
            return array[tail--];
        }
    
        public boolean isEmpty() {
            return head > tail;
        }
    }
    
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n == 0) {
            return new int[0];
        }
    
        Lst lst = new Lst(nums.length + 1);
    
        int[] result = new int[n - k + 1];
        int index = 0;
    
        for (int i = 0; i < k; i++) {
            if (lst.isEmpty()) {
                lst.append(i);
                continue;
            }
    
            int a = nums[i];
            while (!lst.isEmpty() && nums[lst.last()] < a) {
                lst.popLast();
            }
            lst.append(i);
        }
        result[index++] = nums[lst.first()];
    
        for (int i = k; i < n; i++) {
    
            while (!lst.isEmpty() && lst.first() + k <= i) {
                lst.popFirst();
            }
            int a = nums[i];
            while (!lst.isEmpty() && nums[lst.last()] < a) {
                lst.popLast();
            }
            lst.append(i);
    
            result[index++] = nums[lst.first()];
        }
        return result;
    }

  • 0
    G

    Hi ,

    Thanks for taking time to post this solution. It would have been better if you provide explanation than pasting your code. Since it is algorithm its more desirable to get the feel of the algorithm and idea itself than the code.

    Regards,
    Guru


Log in to reply
 

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