O(N lg K) solution


  • 0
    J
    public class Solution {
            public int[] maxSlidingWindow(int[] nums, int k) {
               if (nums == null || nums.length == 0 || k <= 0) {
                    return new int[0];
                }
        
                final int N = nums.length;
                final int[] maxs = new int[N - k + 1];
        
                int ind = 0;
                final TreeMap<Integer, Integer> window = new TreeMap<>();
        
                for (; ind < k; ind++) {
                    incr(window, nums[ind]);
                }
        
                for (; ind <= N; ind++) {
                    maxs[ind - k] = window.lastKey();
                    if (ind == N) {
                        break;
                    }
                    decr(window, nums[ind - k]);
                    incr(window, nums[ind]);
                }
                return maxs;
            }
            
            private void incr(TreeMap<Integer, Integer> window, int num) {
                final int count = window.containsKey(num) ? window.get(num) : 0;
                window.put(num, count + 1);
            }
        
            private void decr(TreeMap<Integer, Integer> window, int num) {
                final int count = window.get(num);
                if(count == 1) {
                    window.remove(num);
                } else {
                    window.put(num, count - 1);
                }
            }
    }

Log in to reply
 

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