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

2021年4月2日10:32:16 发表评论 718 次浏览

## 本文概述

``````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 = 5

Input: 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``````

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

a = [ 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#

``````// 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``````

``9 7 6 8 8 8 5``

• 时间复杂度：O(n)。
仅需要两次遍历数组。因此, 时间复杂度为O(n)。
• 空间复杂度：O(n)。
需要两个大小为n的额外空间。