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

• 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])){
}else{
Set<Integer> temp = new HashSet<>();
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]))
else{
Set<Integer> temp = new HashSet<>();
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();