Input:

1. Array of integers.

2. An integer 'w' which is the window size.

Output:

1. An array of integers, representing the maximum values in all contiguous subarrays of size 'w'.

Algorithm

uses a deque to efficiently keep track of the maximum element in the current window of size 'w'. It ensures that the first element in the deque is always the maximum element in the current window, and as the window slides, it updates the deque and the result array accordingly. This approach achieves an overall time complexity of O(n), making it more efficient than a naive approach that would have a time complexity of O(nw), where 'n' is the size of the input array and 'w' is the window size.

C++

// Online C++ compiler to run C++ program online
#include<iostream>
#include<deque>
#include<vector>
#include<cstdlib>

using namespace std;

vector<int> getMaxWindow(vector<int> arr, int w) {
    if (arr.empty() || w < 1 || arr.size() < w) {
        return vector<int>();
    }
    deque<int> qmax;
    vector<int> res(arr.size() - w + 1);
    int index = 0;
    for (int R = 0; R < arr.size(); R++) {
        while (!qmax.empty() && arr[qmax.back()] <= arr[R]) {
            qmax.pop_back();
        }
        qmax.push_back(R);
        if (qmax.front() == R - w) {
            qmax.pop_front();
        }
        if (R >= w - 1) {
            res[index++] = arr[qmax.front()];
        }
    }
    return res;
}

int main() {
    vector<int> arr = {1,2,3,4,5,6,7,8,9};
    int w = 3;
    vector<int> res = getMaxWindow(arr, w);
    for(int i = 0; i < res.size(); i++) {
        cout << res[i] << " ";
    }
    return 0;
}

Rust

use std::collections::VecDeque;

fn get_max_window(arr: &[i32], w: usize) -> Vec<i32> {
    if w < 1 || arr.len() < w {
        return vec![];
    }
    let mut qmax = VecDeque::new();
    let mut res = vec![0; arr.len() - w + 1];
    let mut index = 0;
    for r in 0..arr.len() {
        while !qmax.is_empty() && arr[*qmax.back().unwrap()] <= arr[r] {
            qmax.pop_back();
        }
        qmax.push_back(r);
        if r >= w && qmax.front().unwrap() == &(r - w) {
            qmax.pop_front();
        }
        if r >= w - 1 {
            res[index] = arr[*qmax.front().unwrap()];
            index += 1;
        }
    }
    res
}

fn main() {
    let arr = vec![1, 2, 3, 4, 5, 6, 7, 8, 9];
    let w = 3;
    let res = get_max_window(&arr, w);
    for i in res {
        println!("{}", i);
    }
}

Python

from collections import deque
import random
def getMaxWindow(arr, w):
    if arr is None or w < 1 or len(arr) < w:
        return None
    qmax = deque()
    res = [0] * (len(arr) - w + 1)
    index = 0
    for R in range(len(arr)):
        while qmax and arr[qmax[-1]] <= arr[R]:
            qmax.pop()
        qmax.append(R)
        if qmax[0] == R - w:
            qmax.popleft()
        if R >= w - 1:
            res[index] = arr[qmax[0]]
            index += 1
    return res

def rightWay(arr, w):
    if arr is None or w < 1 or len(arr) < w:
        return None
    res = [0] * (len(arr) - w + 1)
    index = 0
    L = 0
    R = w - 1
    while R < len(arr):
        max_val = max(arr[L:R+1])
        res[index] = max_val
        index += 1
        L += 1
        R += 1
    return res

def generateRandomArray(maxSize, maxValue):
    import random
    arr = [random.randint(0, maxValue) for _ in range(random.randint(1, maxSize + 1))]
    return arr

def isEqual(arr1, arr2):
    if arr1 is None and arr2 is None:
        return True
    if arr1 is None or arr2 is None or len(arr1) != len(arr2):
        return False
    for i in range(len(arr1)):
        if arr1[i] != arr2[i]:
            return False
    return True

def test():
    testTime = 100000
    maxSize = 100
    maxValue = 100
    print("test begin")
    for i in range(testTime):
        arr = generateRandomArray(maxSize, maxValue)
        w = random.randint(0, len(arr))
        ans1 = getMaxWindow(arr, w)
        ans2 = rightWay(arr, w)
        if not isEqual(ans1, ans2):
            print("Oops!")
    print("test finish")

if __name__ == "__main__":
    test()