# Sliding Window Maximum - Miscellaneous / Monotonic Stack

I don’t think you need to keep track of the number’s index in the queue itself since you only need to start sliding the window once you’ve checked at least k numbers. In other words, you only need to start shifting the window inside the i >= k - 1 check. You also don’t need it to keep track of what to dequeue when shifting the window, even if there are repeats, since you can derive what number needs to be dequeued from checking if the first number in the queue matches nums[i - k + 1]. I like this approach better.

``````    const queue = [];
const res = [];

for (let i = 0; i < nums.length; i++) {
// Pop last num in queue while it's less than new num to be added
while (queue.length > 0 && queue[queue.length - 1] < nums[i]) {
queue.pop();
}
queue.push(nums[i]);

// If we've checked at least k elements, start pushing to res
if (i >= k - 1) {
// Only push largest num in queue which will always be the first num.
res.push(queue);
// Move left part of window over by 1.
// Index to be dequeued will be i - k + 1.
// If queue matches the num to be dequeued, dequeue it.
const dequeueIndex = i - k + 1;
if (queue === nums[i - k + 1]) {
queue.shift();
}
}
}

return res;
``````

My Solution, without stacking the indices,

def sliding_window_maximum(nums: List[int], k: int) → List[int]:
res = []
stack = []
for i in range(len(nums)):
while stack and nums[i] > stack[-1]:
stack.pop()
stack.append(nums[i])
# make sure i-k is valid, and pop it out from the stack/deque at the left when equals to nums[i-k]
if i>=k and stack == nums[i-k]:
stack.pop(0)
if i >= k-1:
res.append(stack)
return res

Repost because of the format issue
from typing import List

def sliding_window_maximum(nums: List[int], k: int) → List[int]:
res = []
stack = []
for i in range(len(nums)):
while stack and nums[i] > stack[-1]:
stack.pop()
stack.append(nums[i])
# make sure i-k is valid, and pop it out from the stack/deque at the left when equals to nums[i-k]
if i>=k and stack == nums[i-k]:
stack.pop(0)
if i >= k-1:
res.append(stack)
return res

Another solution that uses Priority Queue

public static List slidingWindowMaximum(List nums, int k) {

``````    PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
List<Integer> result = new ArrayList<>();

for(int i = 0; i < nums.size(); i++)
{

if (pq.size() == k + 1) // clean the item after when the window shifts
pq.remove(nums.get(i - k));

if (pq.size() == k)
I didn’t get how to use Heap here, because if we build Heap using `indexes`, how can we find the maximum `value`? Or if we use `values`, how can we remove the leftmost `index` from Heap?