TreeMap Solution O(nlogk) and Deque Solution O(n)


  • 4

    TreeMap Solution

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0)
            return nums;
        int[] res = new int[nums.length - k + 1];
        TreeMap<Integer, Set<Integer>> memo = new TreeMap<>();
        for(int i = 0 ; i < k ; i++){
            if(memo.containsKey(nums[i])){
                memo.get(nums[i]).add(i);
            }else{
                Set<Integer> temp = new HashSet<>();
                temp.add(i);
                memo.put(nums[i], temp);
            }
        }
        res[0] = memo.lastKey();
        for(int i = k ; i < nums.length ; i++){
            if(memo.get(nums[i - k]).size() == 1){
                memo.remove(nums[i - k]);
            }else{
                memo.get(nums[i - k]).remove(i - k);
            }
            if(memo.containsKey(nums[i]))
                memo.get(nums[i]).add(i);
            else{
                Set<Integer> temp = new HashSet<>();
                temp.add(i);
                memo.put(nums[i], temp);
            }
            res[i - k + 1] = memo.lastKey();
        }
        return res;
    }
    

    Deque Solution

    public int[] maxSlidingWindow(int[] nums, int k) {
        if(nums.length == 0)
            return nums;
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> memo = new ArrayDeque<>();
        for(int i = 0  ; i < nums.length ; i++){
            while(memo.size() > 0 && memo.getLast() < nums[i])
                memo.removeLast();
            memo.add(nums[i]);
            if(i < k - 1)
                continue;
            res[i - k + 1] = memo.peek();
            if(nums[i - k + 1] == res[i - k + 1])
                memo.removeFirst();
        }
        return res;
    }

Log in to reply
 

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