Dado un arreglo y un entero K , encuentre el máximo para todos y cada uno de los subarreglo contiguos de tamaño k.
Ejemplos:
C++
// C++ Program to find the maximum for
// each and every contiguous subarray of size k.
#include <bits/stdc++.h>
using namespace std;
// Method to find the maximum for each
// and every contiguous subarray of size k.
void printKMax(int arr[], int n, int k)
{
int j, max;
for (int i = 0; i <= n - k; i++)
{
max = arr[i];
for (j = 1; j < k; j++)
{
if (arr[i + j] > max)
max = arr[i + j];
}
cout << max << " ";
}
}
// Driver code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printKMax(arr, n, k);
return 0;
}
// This code is contributed by rathbhupendra
C
#include <stdio.h>
void printKMax(int arr[], int n, int k)
{
int j, max;
for (int i = 0; i <= n - k; i++) {
max = arr[i];
for (j = 1; j < k; j++) {
if (arr[i + j] > max)
max = arr[i + j];
}
printf("%d ", max);
}
}
// Driver Code
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printKMax(arr, n, k);
return 0;
}
Java
// Java Program to find the maximum
// for each and every contiguous
// subarray of size k.
public class GFG
{
// Method to find the maximum for
// each and every contiguous
// subarray of size k.
static void printKMax(int arr[], int n, int k)
{
int j, max;
for (int i = 0; i <= n - k; i++) {
max = arr[i];
for (j = 1; j < k; j++) {
if (arr[i + j] > max)
max = arr[i + j];
}
System.out.print(max + " ");
}
}
// Driver code
public static void main(String args[])
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 3;
printKMax(arr, arr.length, k);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to find the maximum for # each and every contiguous subarray of # size k # Method to find the maximum for each # and every contiguous subarray # of size k def printMax(arr, n, k): max = 0 for i in range(n - k + 1): max = arr[i] for j in range(1, k): if arr[i + j] > max: max = arr[i + j] print(str(max) + " ", end = "") # Driver method if __name__=="__main__": arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] n = len(arr) k = 3 printMax(arr, n, k) # This code is contributed by Shiv Shankar
C#
// C# program to find the maximum for
// each and every contiguous subarray of
// size kusing System;
using System;
class GFG {
// Method to find the maximum for
// each and every contiguous subarray
// of size k.
static void printKMax(int[] arr, int n, int k)
{
int j, max;
for (int i = 0; i <= n - k; i++) {
max = arr[i];
for (j = 1; j < k; j++) {
if (arr[i + j] > max)
max = arr[i + j];
}
Console.Write(max + " ");
}
}
// Driver method
public static void Main()
{
int[] arr = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
int k = 3;
printKMax(arr, arr.Length, k);
}
}
// This Code is Contributed by Sam007
PHP
<?php
// PHP program to find the maximum
// for each and every contiguous
// subarray of size k
function printKMax($arr, $n, $k)
{
$j; $max;
for ($i = 0; $i <= $n - $k; $i++)
{
$max = $arr[$i];
for ($j = 1; $j < $k; $j++)
{
if ($arr[$i + $j] > $max)
$max = $arr[$i + $j];
}
printf("%d ", $max);
}
}
// Driver Code
$arr = array(1, 2, 3, 4, 5,
6, 7, 8, 9, 10);
$n = count($arr);
$k = 3;
printKMax($arr, $n, $k);
// This Code is Contributed by anuj_67.
?>
Javascript
<script>
// JavaScript Program to find the maximum for
// each and every contiguous subarray of size k.
// Method to find the maximum for each
// and every contiguous subarray of size k.
function printKMax(arr,n,k)
{
let j, max;
for (let i = 0; i <= n - k; i++)
{
max = arr[i];
for (j = 1; j < k; j++)
{
if (arr[i + j] > max)
max = arr[i + j];
}
document.write( max + " ");
}
}
// Driver code
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ];
let n =arr.length;
let k = 3;
printKMax(arr, n, k);
// This code contributed by gauravrajput1
</script>
C++14
// C++ program to delete a node from AVL Tree
#include<bits/stdc++.h>
using namespace std;
// An AVL tree node
class Node
{
public:
int key;
Node *left;
Node *right;
int height;
};
// A utility function to get maximum
// of two integers
int max(int a, int b);
// A utility function to get height
// of the tree
int height(Node *N)
{
if (N == NULL)
return 0;
return N->height;
}
// A utility function to get maximum
// of two integers
int max(int a, int b)
{
return (a > b)? a : b;
}
/* Helper function that allocates a
new node with the given key and
NULL left and right pointers. */
Node* newNode(int key)
{
Node* node = new Node();
node->key = key;
node->left = NULL;
node->right = NULL;
node->height = 1; // new node is initially
// added at leaf
return(node);
}
// A utility function to right
// rotate subtree rooted with y
// See the diagram given above.
Node *rightRotate(Node *y)
{
Node *x = y->left;
Node *T2 = x->right;
// Perform rotation
x->right = y;
y->left = T2;
// Update heights
y->height = max(height(y->left),
height(y->right)) + 1;
x->height = max(height(x->left),
height(x->right)) + 1;
// Return new root
return x;
}
// A utility function to left
// rotate subtree rooted with x
// See the diagram given above.
Node *leftRotate(Node *x)
{
Node *y = x->right;
Node *T2 = y->left;
// Perform rotation
y->left = x;
x->right = T2;
// Update heights
x->height = max(height(x->left),
height(x->right)) + 1;
y->height = max(height(y->left),
height(y->right)) + 1;
// Return new root
return y;
}
// Get Balance factor of node N
int getBalance(Node *N)
{
if (N == NULL)
return 0;
return height(N->left) -
height(N->right);
}
Node* insert(Node* node, int key)
{
/* 1. Perform the normal BST rotation */
if (node == NULL)
return(newNode(key));
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // Equal keys not allowed
return node;
/* 2. Update height of this ancestor node */
node->height = 1 + max(height(node->left),
height(node->right));
/* 3. Get the balance factor of this
ancestor node to check whether
this node became unbalanced */
int balance = getBalance(node);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// Right Right Case
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// Left Right Case
if (balance > 1 && key > node->left->key)
{
node->left = leftRotate(node->left);
return rightRotate(node);
}
// Right Left Case
if (balance < -1 && key < node->right->key)
{
node->right = rightRotate(node->right);
return leftRotate(node);
}
/* return the (unchanged) node pointer */
return node;
}
/* Given a non-empty binary search tree,
return the node with minimum key value
found in that tree. Note that the entire
tree does not need to be searched. */
Node * minValueNode(Node* node)
{
Node* current = node;
/* loop down to find the leftmost leaf */
while (current->left != NULL)
current = current->left;
return current;
}
// Recursive function to delete a node
// with given key from subtree with
// given root. It returns root of the
// modified subtree.
Node* deleteNode(Node* root, int key)
{
// STEP 1: PERFORM STANDARD BST DELETE
if (root == NULL)
return root;
// If the key to be deleted is smaller
// than the root's key, then it lies
// in left subtree
if ( key < root->key )
root->left = deleteNode(root->left, key);
// If the key to be deleted is greater
// than the root's key, then it lies
// in right subtree
else if( key > root->key )
root->right = deleteNode(root->right, key);
// if key is same as root's key, then
// This is the node to be deleted
else
{
// node with only one child or no child
if( (root->left == NULL) ||
(root->right == NULL) )
{
Node *temp = root->left ?
root->left :
root->right;
// No child case
if (temp == NULL)
{
temp = root;
root = NULL;
}
else // One child case
*root = *temp; // Copy the contents of
// the non-empty child
free(temp);
}
else
{
// node with two children: Get the inorder
// successor (smallest in the right subtree)
Node* temp = minValueNode(root->right);
// Copy the inorder successor's
// data to this node
root->key = temp->key;
// Delete the inorder successor
root->right = deleteNode(root->right,
temp->key);
}
}
// If the tree had only one node
// then return
if (root == NULL)
return root;
// STEP 2: UPDATE HEIGHT OF THE CURRENT NODE
root->height = 1 + max(height(root->left),
height(root->right));
// STEP 3: GET THE BALANCE FACTOR OF
// THIS NODE (to check whether this
// node became unbalanced)
int balance = getBalance(root);
// If this node becomes unbalanced,
// then there are 4 cases
// Left Left Case
if (balance > 1 &&
getBalance(root->left) >= 0)
return rightRotate(root);
// Left Right Case
if (balance > 1 &&
getBalance(root->left) < 0)
{
root->left = leftRotate(root->left);
return rightRotate(root);
}
// Right Right Case
if (balance < -1 &&
getBalance(root->right) <= 0)
return leftRotate(root);
// Right Left Case
if (balance < -1 &&
getBalance(root->right) > 0)
{
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// A utility function to print preorder
// traversal of the tree.
// The function also prints height
// of every node
void preOrder(Node *root)
{
if(root != NULL)
{
cout << root->key << " ";
preOrder(root->left);
preOrder(root->right);
}
}
// Returns maximum value in a given
// Binary Tree
int findMax(Node* root)
{
// Base case
if (root == NULL)
return INT_MIN;
// Return maximum of 3 values:
// 1) Root's data 2) Max in Left Subtree
// 3) Max in right subtree
int res = root->key;
int lres = findMax(root->left);
int rres = findMax(root->right);
if (lres > res)
res = lres;
if (rres > res)
res = rres;
return res;
}
// Method to find the maximum for each
// and every contiguous subarray of size k.
void printKMax(int arr[], int n, int k)
{
int c = 0,l=0;
Node *root = NULL;
//traverse the array ;
for(int i=0; i<n; i++)
{
c++;
//insert the element in BST
root = insert(root, arr[i]);
//size of subarray greater than k
if(c > k)
{
root = deleteNode(root, arr[l++]);
c--;
}
//size of subarray equal to k
if(c == k)
{
cout<<findMax(root)<<" ";
}
}
}
// Driver code
int main()
{
int arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, k = 4;
int n = sizeof(arr) / sizeof(arr[0]);
printKMax(arr, n, k);
return 0;
}
Java
// JAVA program to delete a node from AVL Tree
import java.io.*;
import java.util.*;
class GFG {
static ArrayList<Integer> findKMaxElement(int[] arr,
int k, int n)
{
// creating the max heap ,to get max element always
PriorityQueue<Integer> queue = new PriorityQueue<>(
Collections.reverseOrder());
ArrayList<Integer> res = new ArrayList<>();
int i = 0;
for (; i < k; i++)
queue.add(arr[i]);
// adding the maximum element among first k elements
res.add(queue.peek());
// removing the first element of the array
queue.remove(arr[0]);
// iterarting for the next elements
for (; i < n; i++) {
// adding the new element in the window
queue.add(arr[i]);
// finding & adding the max element in the
// current sliding window
res.add(queue.peek());
// finally removing the first element from front
// end of queue
queue.remove(arr[i - k + 1]);
}
return res;
// this code is Contributed by Pradeep Mondal P
}
// Driver Code
public static void main(String[] args)
{
int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };
int k = 4, n = arr.length;
List<Integer> res = findKMaxElement(arr, k, n);
for (int x : res)
System.out.print(x + " ");
}
}
Python3
# Python code for the above approach def findKMaxElement(arr, k, n): # creating the max heap ,to get max element always queue = [] res = [] i = 0 while(i<k): queue.append(arr[i]) i += 1 queue.sort(reverse=True) # adding the maximum element among first k elements res.append(queue[0]) # removing the first element of the array queue.remove(arr[0]) # iterarting for the next elements while(i<n): # adding the new element in the window queue.append(arr[i]) queue.sort(reverse=True) # finding & adding the max element in the # current sliding window res.append(queue[0]) # finally removing the first element from front # end of queue queue.remove(arr[i - k + 1]) i += 1 return res # Driver Code arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13] k,n = 4,len(arr) res = findKMaxElement(arr, k, n) for x in res: print(x ,end = " ") # This code is contributed by shinjanpatra
C#
// C# program to delete a node from AVL Tree
using System;
using System.Collections.Generic;
public class GFG {
static List<int> findKMaxElement(int[] arr, int k,
int n)
{
// creating the max heap ,to get max element always
List<int> queue = new List<int>();
List<int> res = new List<int>();
int i = 0;
for (; i < k; i++)
queue.Add(arr[i]);
queue.Sort();
queue.Reverse();
// adding the maximum element among first k elements
res.Add(queue[0]);
// removing the first element of the array
queue.Remove(arr[0]);
// iterarting for the next elements
for (; i < n; i++) {
// adding the new element in the window
queue.Add(arr[i]);
queue.Sort();
queue.Reverse();
// finding & adding the max element in the
// current sliding window
res.Add(queue[0]);
// finally removing the first element from front
// end of queue
queue.Remove(arr[i - k + 1]);
}
return res;
// this code is Contributed by Pradeep Mondal P
}
// Driver Code
public static void Main(String[] args)
{
int[] arr = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };
int k = 4, n = arr.Length;
List<int> res = findKMaxElement(arr, k, n);
foreach(int x in res) Console.Write(x + " ");
}
}
// This code is contributed by umadevi9616
Javascript
<script>
// JAVAscript program to delete a node from AVL Tree
function findKMaxElement(arr, k, n)
{
// creating the max heap ,to get max element always
let queue = [];
let res = [];
let i = 0;
for (; i < k; i++)
queue.push(arr[i]);
queue.sort(function(a,b){return b-a;});
// adding the maximum element among first k elements
res.push(queue[0]);
// removing the first element of the array
queue.splice(arr[0],1);
// iterarting for the next elements
for (; i < n; i++) {
// adding the new element in the window
queue.push(arr[i]);
queue.sort(function(a,b){return b-a;});
// finding & adding the max element in the
// current sliding window
res.push(queue[0]);
// finally removing the first element from front
// end of queue
queue.splice(arr[i - k + 1],1);
}
return res;
// this code is Contributed by Pradeep Mondal P
}
// Driver Code
let arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13];
let k = 4, n = arr.length;
let res = findKMaxElement(arr, k, n);
for (let x of res)
document.write(x + " ");
// This code is contributed by avanitrachhadiya2155
</script>
C++
// CPP program for the above approach
#include <bits/stdc++.h>
using namespace std;
// A Dequeue (Double ended queue) based
// method for printing maximum element of
// all subarrays of size k
void printKMax(int arr[], int n, int k)
{
// Create a Double Ended Queue,
// Qi that will store indexes
// of array elements
// The queue will store indexes
// of useful elements in every
// window and it will
// maintain decreasing order of
// values from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()]
// are sorted in decreasing order
std::deque<int> Qi(k);
/* Process first k (or first window)
elements of array */
int i;
for (i = 0; i < k; ++i)
{
// For every element, the previous
// smaller elements are useless so
// remove them from Qi
while ((!Qi.empty()) && arr[i] >=
arr[Qi.back()])
// Remove from rear
Qi.pop_back();
// Add new element at rear of queue
Qi.push_back(i);
}
// Process rest of the elements,
// i.e., from arr[k] to arr[n-1]
for (; i < n; ++i)
{
// The element at the front of
// the queue is the largest element of
// previous window, so print it
cout << arr[Qi.front()] << " ";
// Remove the elements which
// are out of this window
while ((!Qi.empty()) && Qi.front() <=
i - k)
// Remove from front of queue
Qi.pop_front();
// Remove all elements
// smaller than the currently
// being added element (remove
// useless elements)
while ((!Qi.empty()) && arr[i] >=
arr[Qi.back()])
Qi.pop_back();
// Add current element at the rear of Qi
Qi.push_back(i);
}
// Print the maximum element
// of last window
cout << arr[Qi.front()];
}
// Driver code
int main()
{
int arr[] = { 12, 1, 78, 90, 57, 89, 56 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 3;
printKMax(arr, n, k);
return 0;
}
Java
// Java Program to find the maximum for
// each and every contiguous subarray of size k.
import java.util.Deque;
import java.util.LinkedList;
public class SlidingWindow
{
// A Dequeue (Double ended queue)
// based method for printing
// maximum element of
// all subarrays of size k
static void printMax(int arr[], int n, int k)
{
// Create a Double Ended Queue, Qi
// that will store indexes of array elements
// The queue will store indexes of
// useful elements in every window and it will
// maintain decreasing order of values
// from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()]
// are sorted in decreasing order
Deque<Integer> Qi = new LinkedList<Integer>();
/* Process first k (or first window)
elements of array */
int i;
for (i = 0; i < k; ++i)
{
// For every element, the previous
// smaller elements are useless so
// remove them from Qi
while (!Qi.isEmpty() && arr[i] >=
arr[Qi.peekLast()])
// Remove from rear
Qi.removeLast();
// Add new element at rear of queue
Qi.addLast(i);
}
// Process rest of the elements,
// i.e., from arr[k] to arr[n-1]
for (; i < n; ++i)
{
// The element at the front of the
// queue is the largest element of
// previous window, so print it
System.out.print(arr[Qi.peek()] + " ");
// Remove the elements which
// are out of this window
while ((!Qi.isEmpty()) && Qi.peek() <=
i - k)
Qi.removeFirst();
// Remove all elements smaller
// than the currently
// being added element (remove
// useless elements)
while ((!Qi.isEmpty()) && arr[i] >=
arr[Qi.peekLast()])
Qi.removeLast();
// Add current element at the rear of Qi
Qi.addLast(i);
}
// Print the maximum element of last window
System.out.print(arr[Qi.peek()]);
}
// Driver code
public static void main(String[] args)
{
int arr[] = { 12, 1, 78, 90, 57, 89, 56 };
int k = 3;
printMax(arr, arr.length, k);
}
}
// This code is contributed by Sumit Ghosh
Python3
# Python program to find the maximum for # each and every contiguous subarray of # size k from collections import deque # A Deque (Double ended queue) based # method for printing maximum element # of all subarrays of size k def printMax(arr, n, k): """ Create a Double Ended Queue, Qi that will store indexes of array elements. The queue will store indexes of useful elements in every window and it will maintain decreasing order of values from front to rear in Qi, i.e., arr[Qi.front[]] to arr[Qi.rear()] are sorted in decreasing order""" Qi = deque() # Process first k (or first window) # elements of array for i in range(k): # For every element, the previous # smaller elements are useless # so remove them from Qi while Qi and arr[i] >= arr[Qi[-1]] : Qi.pop() # Add new element at rear of queue Qi.append(i); # Process rest of the elements, i.e. # from arr[k] to arr[n-1] for i in range(k, n): # The element at the front of the # queue is the largest element of # previous window, so print it print(str(arr[Qi[0]]) + " ", end = "") # Remove the elements which are # out of this window while Qi and Qi[0] <= i-k: # remove from front of deque Qi.popleft() # Remove all elements smaller than # the currently being added element # (Remove useless elements) while Qi and arr[i] >= arr[Qi[-1]] : Qi.pop() # Add current element at the rear of Qi Qi.append(i) # Print the maximum element of last window print(str(arr[Qi[0]])) # Driver code if __name__=="__main__": arr = [12, 1, 78, 90, 57, 89, 56] k = 3 printMax(arr, len(arr), k) # This code is contributed by Shiv Shankar
C#
// C# Program to find the maximum for each
// and every contiguous subarray of size k.
using System;
using System.Collections.Generic;
public class SlidingWindow
{
// A Dequeue (Double ended queue) based
// method for printing maximum element of
// all subarrays of size k
static void printMax(int []arr, int n, int k)
{
// Create a Double Ended Queue, Qi that
// will store indexes of array elements
// The queue will store indexes of useful
// elements in every window and it will
// maintain decreasing order of values
// from front to rear in Qi, i.e.,
// arr[Qi.front[]] to arr[Qi.rear()]
// are sorted in decreasing order
List<int> Qi = new List<int>();
/* Process first k (or first window)
elements of array */
int i;
for (i = 0; i < k; ++i) {
// For every element, the previous
// smaller elements are useless so
// remove them from Qi
while (Qi.Count != 0 && arr[i] >=
arr[Qi[Qi.Count-1]])
// Remove from rear
Qi.RemoveAt(Qi.Count-1);
// Add new element at rear of queue
Qi.Insert(Qi.Count, i);
}
// Process rest of the elements,
// i.e., from arr[k] to arr[n-1]
for (; i < n; ++i)
{
// The element at the front of
// the queue is the largest element of
// previous window, so print it
Console.Write(arr[Qi[0]] + " ");
// Remove the elements which are
// out of this window
while ((Qi.Count != 0) && Qi[0] <= i - k)
Qi.RemoveAt(0);
// Remove all elements smaller
// than the currently
// being added element (remove
// useless elements)
while ((Qi.Count != 0) && arr[i] >=
arr[Qi[Qi.Count - 1]])
Qi.RemoveAt(Qi.Count - 1);
// Add current element at the rear of Qi
Qi.Insert(Qi.Count, i);
}
// Print the maximum element of last window
Console.Write(arr[Qi[0]]);
}
// Driver code
public static void Main(String[] args)
{
int []arr = { 12, 1, 78, 90, 57, 89, 56 };
int k = 3;
printMax(arr, arr.Length, k);
}
}
// This code has been contributed by 29AjayKumar
C++
#include <bits/stdc++.h>
using namespace std;
struct node{
int data;
int maximum;
};
// it is a modification in the way of implementation of queue using two stack
void insert(stack<node> &s2 , int val)
{
//inserting the element in s2
node other;
other.data=val;
if(s2.empty()) other.maximum=val;
else
{
node front=s2.top();
//updating maximum in that stack push it
other.maximum=max(val,front.maximum);
}
s2.push(other);
return;
}
void delete(stack<node> &s1 ,stack<node> &s2 )
{
//if s1 is not empty directly pop
//else we have to push all element from s2 and thatn pop from s1
//while pushing from s2 to s1 update maximum variable in s1
if(s1.size()) s1.pop();
else
{
while(!s2.empty())
{
node val=s2.top();
insert(s1,val.data);
s2.pop();
}
s1.pop();
}
}
int get_max(stack<node> &s1 ,stack<node> &s2 )
{
// the maximum of both stack will be the maximum of overall window
int ans=-1;
if(s1.size()) ans=max(ans,s1.top().maximum);
if(s2.size()) ans=max(ans,s2.top().maximum);
return ans;
}
vector<int> slidingMaximum(int a[], int b,int n) {
//s2 for push
//s1 for pop
vector<int>ans;
stack<node>s1,s2;
//shifting all value except the last one if first window
for(int i=0;i<b-1;i++) insert(s2,a[i]);
for(int i=0;i<=n-b;i++)
{
//removing the last element of previous window as window has shift by one
if(i-1>=0) delete(s1,s2);
//adding the new element to the window as the window is shift by one
insert(s2,a[i+b-1]);
ans.push_back(get_max(s1,s2));
}
return ans;
}
int main()
{
int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 4;
vector<int> ans=slidingMaximum(arr,k,n);
for(auto x:ans) cout<<x<<" ";
return 0;
}
Java
/*package whatever //do not write package name here */
import java.io.*;
import java.util.*;
class GFG {
static class node{
public int data;
public int maximum;
public node(int data,int maximum){
this.data = data;
this.maximum = maximum;
}
}
// it is a modification in the way
// of implementation of queue using two stack
static void insert(Stack<node>s2 , int val)
{
// inserting the element in s2
node other = new node(0,0);
other.data=val;
if(s2.size() == 0) other.maximum=val;
else
{
node front=s2.peek();
// updating maximum in that stack push it
other.maximum = Math.max(val,front.maximum);
}
s2.add(other);
return;
}
static void delete(Stack<node>s1 ,Stack<node>s2)
{
// if s1 is not empty directly pop
// else we have to push all element from s2 and thatn pop from s1
// while pushing from s2 to s1 update maximum variable in s1
if(!s1.empty()) s1.pop();
else
{
while(!s2.empty())
{
node val=s2.peek();
insert(s1,val.data);
s2.pop();
}
s1.pop();
}
}
static int get_max(Stack<node>s1 ,Stack<node>s2)
{
// the maximum of both stack will be the maximum of overall window
int ans = -1;
if(s1.size() > 0) ans = Math.max(ans,s1.peek().maximum);
if(s2.size() > 0) ans = Math.max(ans,s2.peek().maximum);
return ans;
}
static ArrayList<Integer> slidingMaximum(int a[], int b,int n) {
// s2 for push
// s1 for pop
ArrayList<Integer>ans = new ArrayList<>();
Stack<node>s1 = new Stack<>(),s2 = new Stack<>();
// shifting all value except the last one if first window
for(int i=0;i<b-1;i++) insert(s2,a[i]);
for(int i=0;i<=n-b;i++)
{
// removing the last element of previous
// window as window has shift by one
if(i-1>=0) delete(s1,s2);
// adding the new element to
// the window as the window is shift by one
insert(s2,a[i+b-1]);
ans.add(get_max(s1,s2));
}
return ans;
}
// Driver Code
public static void main(String args[])
{
int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 };
int n = arr.length;
int k = 4;
ArrayList<Integer> ans=slidingMaximum(arr,k,n);
for(int x:ans)
{
System.out.printf("%d ",x);
}
}
}
// This code is contributed by shinjanpatra
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA