<gh_stars>0
import math


def max_in_window(array, win_size):
    max_val = max(array[:win_size])
    max_idx = array[:win_size].index(max_val)
    array_max = [max_val]

    for i in range(1, len(array) - win_size + 1):
        new_idx = i + win_size - 1
        new_val = array[new_idx]
        if max_idx >= i:
            max_val = max(max_val, new_val)
            max_idx = new_idx if max_val <= new_val else max_idx

        else:
            max_val = max(array[i : i + win_size])
            max_idx = array[i : i + win_size].index(max_val) + i

        array_max.append(max_val)

    print(array_max)


class monoque:
    def __init__(self) -> None:
        self.queue = []

    def push(self, d):
        while self.queue and self.queue[-1] <= d:
            self.queue.pop()
        self.queue.append(d)

    def pop(self, d):
        if self.queue and d == self.queue[0]:
            self.queue.pop(0)


def winmax(data, size):
    q = monoque()
    for i in range(size):
        q.push(data[i])

    result = [q.queue[0]]

    for i in range(size, len(data)):

        q.pop(data[i - size])
        q.push(data[i])
        result.append(q.queue[0])
    print(result)
    return result


max_in_window([1, 3, -1, -3, 5, 3, 6, 7], 3)
winmax([1, 3, -1, -3, 5, 3, 6, 7], 3)


import math


def max_in_window(array, win_size):
    max_val = max(array[:win_size])
    max_idx = array[:win_size].index(max_val)
    array_max = [max_val]

    for i in range(1, len(array) - win_size + 1):
        new_idx = i + win_size - 1
        new_val = array[new_idx]
        if max_idx >= i:
            max_val = max(max_val, new_val)
            max_idx = new_idx if max_val <= new_val else max_idx

        else:
            max_val = max(array[i : i + win_size])
            max_idx = array[i : i + win_size].index(max_val) + i

        array_max.append(max_val)

    print(array_max)


class monoque:
    def __init__(self) -> None:
        self.queue = []

    def push(self, d):
        while self.queue and self.queue[-1] <= d:
            self.queue.pop()
        self.queue.append(d)

    def pop(self, d):
        if self.queue and d == self.queue[0]:
            self.queue.pop(0)


def winmax(data, size):
    q = monoque()
    for i in range(size):
        q.push(data[i])

    result = [q.queue[0]]

    for i in range(size, len(data)):

        q.pop(data[i - size])
        q.push(data[i])
        result.append(q.queue[0])
    print(result)
    return result


max_in_window([1, 3, -1, -3, 5, 3, 6, 7], 3)
winmax([1, 3, -1, -3, 5, 3, 6, 7], 3)