So for the first k elements, we calculate its max then assign to res[0] which res is an int array for return

Then we update when next element comes. If current max still in the interval, just compare to the new element, else we need to find new max in new interval. The worst case is descending order which is O(nk), n is the length of arr. Still can be considered as O(n) if k is a constant.

```
public int[] maxSlidingWindow(int[] arr, int k) {
if(arr.length==0 || k==1) return arr;
int len=arr.length-k+1, i=0, max=arr[0];
// an int array for return
int[] res = new int[len];
// Find max from the first k elements
for (i=0; i<k; i++) {
max = Math.max(arr[i], max);
}
// Assign to res[0]
res[0] = max;
for (i=1; i<len; i++) {
// After add and remove new element, If max is no longer in current round, find it again like first round.
if (arr[i-1] == max) {
max = arr[i];
for (int j=i; j<=i+k-1; j++) {
max = Math.max(arr[j], max);
}
}
// max still in current round, then compare to new added element only
else {
max = Math.max(max, arr[i+k-1]);
}
res[i] = max;
}
return res;
}
```