Maintaining a maximum in the window?

Question

Python

The array moves the window, you need to specify all the maximums on each movement of the window.
This must be done in O(n) time, where n is the length of the array.
I'm new to python, and I'm just learning algorithms, so it's hard to determine the speed.
The question is whether I correctly determined the speed? And does the second algorithm match the problem?
Or the first one?
I did the first one first, but it seems like, in the worst case, it will look for maxima in each window, i.e. -slowly. How to improve?

def pushwindow(array, window):
    """
    возвращает список из максимумов окна в массиве
    худшая скорость квадрат логарифма размера окна
    """
    if window==1: return array
    results=[]
    start = 0
    end = window-1
    len_array = len(array)
    max_window = max(array[:window]) # находит максимум в первом окне
    results.append(max_window)
    while end < len_array-1:  # работает пока окна в пределах массива
        end+=1
        if array[end]>=max_window: # делает новый максимум, если он
            max_window = array[end] # больше предыдущего максимума
            start+=1
        elif max_window!=array[start]: # если текущий максимум не
            start+=1                   # является началом окна максимум
        else:                          # не меняется
            start+=1
            max_window = max(array[start:end+1]) # ищет новый максимум в
        results.append(max_window)               # окне - плохо!!!
    return results

The second one looks better, but I'm not sure. How can it be improved?

def pushwindow2(array, window):
   """
    выводит максимумы при каждом движении окна
    оценка скорости O(2array) не зависит от окна
    """
    results = [array[0]]
    for index, value in enumerate(array[1:]):
        for index2, value2 in enumerate(results): # ставит новый элемент
            if value2 <= value:                   # на место по возрастанию
                results.insert(index2,  value)    # начиная от 0
                break
        else:
            results.append(value)                 # или в конец
        if len(results) == window:                # должно вызывать только один раз
            print (results[0])                    # но проверяется на каждом цикле - плохо!!!
        if len(results) == window+1:
            results.remove(array[index-window+1]) # удаляет элемент из списка при
            print (results[0])                    # движении окна

I would be very grateful for help

Answer 1

Order, I figured it out.
Let's create a list of maximum length w, which contains pairs (index, value) and value is not strictly decreasing. How this list is arranged - we will analyze later.
At first the list is empty. First, perform the “a[i] entered” operation w times. Then n−w times — first "a[i−w] went out", then "а[i] went in". Each time list.front is the index and the max value. element.
Operation "a[i] entered". From the end of the list, remove all elements whose value is less than a[i]. Then we attach the pair (i, a[i]) to the end.
Operation "a[i] is out". If at the beginning of the list index=i, remove the first element. Otherwise, we do nothing.
Why O(n)? The only place where the complexity is not obvious is the deletion in the “a[i] entered” operation. But there will be no more deletions than insertions, and they are exactly O (n) - so no problem.
Well, for dessert - how the list should be arranged.
— Limited length (no more than w).
- Removal from the beginning.
- Insert at the end.
— Removal from the end.
Iterate over familiar data structures. Which is the most suitable? I think it's a roundabout.

Answer 2

Try to read here: e-maxx.ru/algo/stacks_for_minima