# O(n) Java solution

• the code is quite self explaining.

`````` class Lst {
public final int size;
private final int[] array;

Lst(int size) {
this.size = size;
this.array = new int[size];
this.tail = -1;
}

public int first() {
}

public int popFirst() {
}

public void append(int t) {
array[++tail] = t;
}

public int last() {
return array[tail];
}

public int popLast() {
return array[tail--];
}

public boolean isEmpty() {
}
}

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

Lst lst = new Lst(nums.length + 1);

int[] result = new int[n - k + 1];
int index = 0;

for (int i = 0; i < k; i++) {
if (lst.isEmpty()) {
lst.append(i);
continue;
}

int a = nums[i];
while (!lst.isEmpty() && nums[lst.last()] < a) {
lst.popLast();
}
lst.append(i);
}
result[index++] = nums[lst.first()];

for (int i = k; i < n; i++) {

while (!lst.isEmpty() && lst.first() + k <= i) {
lst.popFirst();
}
int a = nums[i];
while (!lst.isEmpty() && nums[lst.last()] < a) {
lst.popLast();
}
lst.append(i);

result[index++] = nums[lst.first()];
}
return result;
}``````

• Hi ,

Thanks for taking time to post this solution. It would have been better if you provide explanation than pasting your code. Since it is algorithm its more desirable to get the feel of the algorithm and idea itself than the code.

Regards,
Guru

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