Java O(nlogk) solution using TreeMap


  • 2
    public class Solution {
        
        public int[] maxSlidingWindow(int[] nums, int k) {
            if(nums.length==0)
                return new int[0];
            int[] res = new int[nums.length-k+1];
            TreeMap<Integer,Integer> tree = new TreeMap<>();
            for(int i=0; i<k; i++)
                add(tree,nums[i]);
            res[0] = tree.lastKey();
            for(int i=k, j=1; i<nums.length; i++, j++) {
                remove(tree, nums[i-k]);
                add(tree, nums[i]);
                res[j] = tree.lastKey();
            }
            return res;
        }
        
        public void add(TreeMap<Integer,Integer> tree, int val) {
            if(tree.containsKey(val))
                tree.put(val, tree.get(val)+1);
            else
                tree.put(val,1);
        }
        
        public void remove(TreeMap<Integer,Integer> tree, int val) {
            if(tree.get(val)>1)
                tree.put(val, tree.get(val)-1);
            else
                tree.remove(val);
        }
    }

Log in to reply
 

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