239. Sliding Window Maximum

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] result = new int[nums.length - k + 1];
        
        int curMax = nums[0];
        int maxLoc = 0;
        int secMax = nums[0];
        int secLoc = 0; 
        
        Queue<Integer> q = new LinkedList<Integer>();
        Map<Integer, Integer> m = new HashMap<Integer, Integer>();
        
        if (k >= nums.length) {
            Arrays.sort(nums);
            return nums[nums.length - 1];
        }
        
        for (int i = 1; i < k; i++) {
            if (nums[i] >= curMax) {
                curMax = nums[i];
                maxLoc = i;
            } else if (nums[i] >= secMax) {
                secMax = nums[i];
                secLoc = i;
            }
            
            q.add(nums[i]);
        }
        
        for (int j = k; j < nums.length; j++) {
            q.remove();
        }
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int n = nums.length;
        if (n * k == 0) return new int[0];
        
        int [] output = new int[n - k + 1];
        for (int i = 0; i < n - k + 1; i++) {
            int max = Integer.MIN_VALUE;
            for(int j = i; j < i + k; j++) 
                max = Math.max(max, nums[j]);
            output[i] = max;
        }
        return output;
    }
}

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int[] check = new int[nums.length];
        Arrays.fill(check, Integer.MIN_VALUE);
        int changed = 0;
        
        Map<Integer, Integer> vals = new HashMap<Integer, Integer>();
        
        for (int i = 0; i < nums.length; i++) {
            vals.put(nums[i], i);
        }
        
        Arrays.sort(nums);
        int j = 0;
        
        int[] result = new int[nums.length - k + 1];
        
        while (changed < nums.length) {
            int m = nums[j];
            int loc = vals.get(m);
            
            for (int l = (loc - k >= 0 ? loc - k : 0); l < (loc + k < nums.length ? loc + k : nums.length - 1); l++) {
                if (check[l] < m) {
                    check[l] = m;
                    j++;
                }
            }
        }
        
        for (int a = 0; a < nums.length - k + 1; a++) {
            result[a] = check[a];
        }
        
        return result;
    }
}

class Solution {
  ArrayDeque<Integer> deq = new ArrayDeque<Integer>();
  int [] nums;

  public void clean_deque(int i, int k) {
    // remove indexes of elements not from sliding window
    if (!deq.isEmpty() && deq.getFirst() == i - k)
      deq.removeFirst();

    // remove from deq indexes of all elements 
    // which are smaller than current element nums[i]
    while (!deq.isEmpty() && nums[i] > nums[deq.getLast()])                           deq.removeLast();
  }

  public int[] maxSlidingWindow(int[] nums, int k) {
    int n = nums.length;
    if (n * k == 0) return new int[0];
    if (k == 1) return nums;

    // init deque and output
    this.nums = nums;
    int max_idx = 0;
    for (int i = 0; i < k; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      // compute max in nums[:k]
      if (nums[i] > nums[max_idx]) max_idx = i;
    }
    int [] output = new int[n - k + 1];
    output[0] = nums[max_idx];

    // build output
    for (int i  = k; i < n; i++) {
      clean_deque(i, k);
      deq.addLast(i);
      output[i - k + 1] = nums[deq.getFirst()];
    }
    return output;
  }
}