Sliding Window Maximum

You are given an array of integers, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

Return the max sliding window.

Example:

Input:  arr[]={1,3,-1,-3,5,3,6,7},k=3
Output: maximum[]={3,3,5,5,6,7}

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
public class SlidingWindowMaximum {
    public static void main(String[] args) {
        int arr[] = { 1, 3, -1, -3, 5, 3, 6, 7 };
        int k = 3;
        List<Integer> res = maxSlidingWindow(arr, k);
        System.out.println(Arrays.asList(res));
    }
    // functiom to get the maximum value in the window
    static int getmax(Stack<Pair<Integer, Integer>> st1, Stack<Pair<Integer, Integer>> st2) {
        // if any stack is empty then return the top
        // element of one which is non empty
        if (st1.isEmpty() || st2.isEmpty())
            return st1.isEmpty() ? st2.peek().getValue() : st1.peek().getValue();
        // else return the maximum of both the stacks
        return Math.max(st1.peek().getValue(), st2.peek().getValue());
    }
    // function to add new element
    static void addElem(Stack<Pair<Integer, Integer>> st1, int new_element) {
        // find the new maximum value if
        // stack is empty then maximum is the current element
        // else the maximum is max of cuurent element and top of stack
        int max1 = st1.isEmpty() ? new_element : Math.max(new_element, st1.peek().getValue());
        // push into the stack with new max
        st1.add(new Pair(new_element, max1));
    }
    // function to remove the element
    static void remove(Stack<Pair<Integer, Integer>> st1, Stack<Pair<Integer, Integer>> st2) {
        // if stack 2 is empty
        if (st2.isEmpty()) {
            // put all of stack one into stack 2
            // means convert into the queue
            while (!st1.isEmpty()) {
                int element = st1.pop().getKey();
                int max1 = st2.isEmpty() ? element : Math.max(element, st2.peek().getValue());
                st2.add(new Pair(element, max1));
            }
        }
        // delete the top element from stack 2
        st2.pop();
    }
    // function to find the maximum in window of
    // given size
    static List<Integer> maxSlidingWindow(int[] nums, int k) {
        Stack<Pair<Integer, Integer>> st1 = new Stack<Pair<Integer, Integer>>();
        Stack<Pair<Integer, Integer>> st2 = new Stack<Pair<Integer, Integer>>();
        // add k elements
        for (int i = 0; i < k; i++)
            addElem(st1, nums[i]);
        List<Integer> res = new ArrayList<Integer>();
        // push into the anwer
        res.add(getmax(st1, st2));
        // iterate for remaining elements
        for (int i = k; i < nums.length; i++) {
            // remove the start element
            remove(st1, st2);
            // add new elements
            addElem(st1, nums[i]);
            // push into the result
            res.add(getmax(st1, st2));
            
        }
        
        return res;
    }
}
class Pair<F, S> {
    private F key;
    private S value;
    public Pair() {
    }
    public Pair(F key, S value) {
        this.key = key;
        this.value = value;
    }
    public F getKey() {
        return key;
    }
    public void setKey(F key) {
        this.key = key;
    }
    public S getValue() {
        return value;
    }
    public void setValue(S value) {
        this.value = value;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
//functiom to get the maximum value in the window
int getmax(stack<pair<int,int>> &st1,stack<pair<int,int>> &st2)
{
    //if any stack is empty then return the top
    //elmemt of one which is non empty
    if(st1.empty()||st2.empty())
        return st1.empty()?st2.top().second:st1.top().second;
    
    //else return the maximum of both the stacks
    return max(st1.top().second,st2.top().second);
}
//function to add new element
void add(stack<pair<int,int>> &st1,int new_element)
{
    //find the new maximum value if
    //stack is empty then maximum is the current element
    //else the maximum is max of cuurent element and top of stack
    int max1=st1.empty()?new_element:max(new_element,st1.top().second);
    //push into the stack with new max
    st1.push({new_element,max1});
}
//function to remove the element
void remove(stack<pair<int,int>> &st1,stack<pair<int,int>> &st2)
{
    //if stack 2 is empty
    if(st2.empty())
     {
         //put all of stack one into stack 2
         //means convert into the queue
        while(!st1.empty())
            {
                int element=st1.top().first;
                st1.pop();
                int max1=st2.empty()?element:max(element,st2.top().second);
                st2.push({element,max1});
            }
    }
    //delete the top element from stack 2
    st2.pop();
}

//function to find the maximum in window of
//given size
vector<int> maxSlidingWindow(vector<int>& nums, int k) 
{
      stack<pair<int,int>> st1,st2;
      //add k elements
        for(int i=0;i<k;i++)
            add(st1,nums[i]);
      vector<int> res;
      //push into the anwer
      res.push_back(getmax(st1,st2));
   
     //inerate for remaining elements
     for(int i=k;i<nums.size();i++)
        {
            //remove the start element
            remove(st1,st2);
            //add new elements
            add(st1,nums[i]);
            //push into the result
            res.push_back(getmax(st1,st2));
        }
        return res;
        
}
int main()
{
   vector<int> arr ={1,3,-1,-3,5,3,6,7};
   int  k = 3;
   vector<int> maximum=maxSlidingWindow(arr,k);
   for(int i=0;i<maximum.size();i++)
      cout<<maximum[i]<<" ";
   return 0;
}