使用O(n)时间的栈的滑动窗口最大值(大小为k的所有子数组的最大值) _数据结构

本文概述

C ++
Java
Python3
C#

给出一个包含N个整数和另一个k≤N的整数的数组arr[]，任务是找到每个大小为k的子数组的最大元素。
例子：

Input: arr[] = {9, 7, 2, 4, 6, 8, 2, 1, 5} k = 3 Output: 9 7 6 8 8 8 5 Explanation: Window 1: {9, 7, 2}, max = 9 Window 2: {7, 2, 4}, max = 7 Window 3: {2, 4, 6}, max = 6 Window 4: {4, 6, 8}, max = 8 Window 5: {6, 8, 2}, max = 8 Window 6: {8, 2, 1}, max = 8 Window 7: {2, 1, 5}, max = 5Input: arr[] = {6, 7, 5, 2, 1, 7, 2, 1, 10} k = 2 Output: 7 7 5 2 7 7 2 10 Explanation: Window 1: {6, 7}, max = 7 Window 2: {7, 5}, max = 7 Window 3: {5, 2}, max = 5 Window 4: {2, 1}, max = 2 Window 5: {1, 7}, max = 7 Window 6: {7, 2}, max = 7 Window 7: {2, 1}, max = 2 Window 8: {1, 10}, max = 10

先决条件：下一个更大的元素
方法：
对于每个索引，计算子数组从这个索引开始时当前元素最大的索引，即对于每个索引i，一个索引j≥i，使max(a[i]， a[i + 1]，…a[j]) = a[i]。我们把它命名为max_upto[i]。
然后，通过检查从i到i + k - 1, max_upto[i]≥i + k - 1(该窗口的最后一个索引)的每个索引，可以找到长度为k的子数组中从第i个索引开始的最大元素。
栈数据结构可以用来在一个窗口中存储值，即最后访问的或之前插入的元素将在顶部(与当前元素的索引最近的元素)。
算法：

创建一个数组max_upto和一个用于存储索引的堆栈。在堆栈中压入0。
运行从索引1到索引n-1的循环。
从堆栈中弹出所有索引, 其中哪些元素(array 展开)小于当前元素并更新max_upto 展开 = i – 1然后将i插入堆栈。
从堆栈中弹出所有索引并分配max_upto 展开 = n – 1.
创建一个变量j = 0
运行从0到n – k的循环, 循环计数器为i
运行一个嵌套循环, 直到j < i或max_upto [j] < i + k – 1, 在每次迭代中递增j。
打印第j个数组元素。

实现
C ++

// C++ implementation of the approach #include < bits/stdc++.h> using namespace std; // Function to print the maximum for // every k size sub-array void print_max( int a[], int n, int k) { // max_upto array stores the index // upto which the maximum element is a[i] // i.e. max(a[i], a[i + 1], ... a[max_upto[i]]) = a[i]int max_upto[n]; // Update max_upto array similar to // finding next greater element stack< int > s; s.push(0); for ( int i = 1; i < n; i++) { while (!s.empty() & & a展开 < a[i]) { max_upto展开 = i - 1; s.pop(); } s.push(i); } while (!s.empty()) { max_upto展开 = n - 1; s.pop(); } int j = 0; for ( int i = 0; i < = n - k; i++) {// j < i is to check whether the // jth element is outside the window while (j < i || max_upto[j] < i + k - 1) j++; cout < < a[j] < < " " ; } cout < < endl; }// Driver code int main() { int a[] = { 9, 7, 2, 4, 6, 8, 2, 1, 5 }; int n = sizeof (a) / sizeof ( int ); int k = 3; print_max(a, n, k); return 0; }

Java

// Java implementation of the approach import java.util.*; class GFG {// Function to print the maximum for // every k size sub-array static void print_max( int a[], int n, int k) { // max_upto array stores the index // upto which the maximum element is a[i] // i.e. max(a[i], a[i + 1], ... a[max_upto[i]]) = a[i]int [] max_upto = new int [n]; // Update max_upto array similar to // finding next greater element Stack< Integer> s = new Stack< > (); s.push( 0 ); for ( int i = 1 ; i < n; i++) { while (!s.empty() & & a展开 < a[i]) { max_upto展开 = i - 1 ; s.pop(); } s.push(i); } while (!s.empty()) { max_upto展开 = n - 1 ; s.pop(); } int j = 0 ; for ( int i = 0 ; i < = n - k; i++) {// j < i is to check whether the // jth element is outside the window while (j < i || max_upto[j] < i + k - 1 ) { j++; } System.out.print(a[j] + " " ); } System.out.println(); }// Driver code public static void main(String[] args) { int a[] = { 9 , 7 , 2 , 4 , 6 , 8 , 2 , 1 , 5 }; int n = a.length; int k = 3 ; print_max(a, n, k); } }// This code has been contributed by 29AjayKumar

Python3

# Python3 implementation of the approach# Function to print the maximum for # every k size sub-array def print_max(a, n, k):# max_upto array stores the index # upto which the maximum element is a[i] # i.e. max(a[i], a[i + 1], ... a[max_upto[i]]) = a[i]max_upto = [ 0 for i in range (n)]# Update max_upto array similar to # finding next greater element s = [] s.append( 0 )for i in range ( 1 , n): while ( len (s) > 0 and a展开] < a[i]): max_upto展开] = i - 1 del s[ - 1 ]s.append(i)while ( len (s) > 0 ): max_upto展开] = n - 1 del s[ - 1 ]j = 0 for i in range (n - k + 1 ):# j < i is to check whether the # jth element is outside the window while (j < i or max_upto[j] < i + k - 1 ): j + = 1 print (a[j], end = " " ) print () # Driver codea = [ 9 , 7 , 2 , 4 , 6 , 8 , 2 , 1 , 5 ] n = len (a) k = 3 print_max(a, n, k)# This code is contributed by mohit kumar

// C# implementation of the approach using System; using System.Collections.Generic; class GFG {// Function to print the maximum for // every k size sub-array static void print_max( int []a, int n, int k) { // max_upto array stores the index // upto which the maximum element is a[i] // i.e. max(a[i], a[i + 1], ... a[max_upto[i]]) = a[i]int [] max_upto = new int [n]; // Update max_upto array similar to // finding next greater element Stack< int > s = new Stack< int > (); s.Push(0); for ( int i = 1; i < n; i++) { while (s.Count!=0 & & a展开 < a[i]) { max_upto展开 = i - 1; s.Pop(); } s.Push(i); } while (s.Count!=0) { max_upto展开 = n - 1; s.Pop(); } int j = 0; for ( int i = 0; i < = n - k; i++) {// j < i is to check whether the // jth element is outside the window while (j < i || max_upto[j] < i + k - 1) { j++; } Console.Write(a[j] + " " ); } Console.WriteLine(); }// Driver code public static void Main(String[] args) { int []a = {9, 7, 2, 4, 6, 8, 2, 1, 5}; int n = a.Length; int k = 3; print_max(a, n, k); } }// This code has been contributed by 29AjayKumar

输出如下：