算法设计：最大滑动窗口-大小为k的所有子数组的最大值 S2

本文概述

• C++
• Java
• Python3
• C#

S1： 最大滑动窗口(大小为k的所有子数组的最大值).

给定一个大小为N和整数K的数组arr，任务是找出每个大小为K的连续子数组的最大值。

例子：

输入：arr [] = {1、2、3、1、4、5、2、3、6}, K = 3
输出：3 3 4 5 5 5 6
所有大小为k的相邻子数组均为
{1、2、2 3} => 3
{2, 3, 1} => 3
{3, 1, 4} => 4
{1, 4, 5} => 5
{4, 5, 2} => 5
{5, 2, 3} => 5
{2, 3, 6} => 6
输入：arr [] = {8, 5, 10, 7, 9, 4, 15, 12, 12, 90, 13}, K = 4
输出：10 10 10 15 15 90 90

方法：为了在较小的空间复杂度中解决此问题, 我们可以使用二指针技术.

• 第一个变量指针遍历子数组并从给定大小中找到最大元素ķ
• 第二个变量指针标记第一个变量指针的结束索引, 即第(i + K – 1)个索引.
• 当第一个变量指针到达第二个变量指针的索引时, 该子数组的最大值已被计算并将被打印。
• 重复该过程, 直到第二个变量指针到达最后一个数组索引为止(即array_size – 1).

下面是上述方法的实现：

C++

//C++ program to find the maximum for each
//and every contiguous subarray of size K
  
#include <bits/stdc++.h>
using namespace std;
  
//Function to find the maximum for each
//and every contiguous subarray of size k
void printKMax( int a[], int n, int k)
{
     //If k = 1, print all elements
     if (k == 1) {
         for ( int i = 0; i <n; i += 1)
             cout <<a[i] <<" " ;
         return ;
     }
  
     //Using p and q as variable pointers
     //where p iterates through the subarray
     //and q marks end of the subarray.
     int p = 0, q = k - 1, t = p, max = a[k - 1];
  
     //Iterating through subarray.
     while (q <= n - 1) {
  
         //Finding max
         //from the subarray.
         if (a
> max)
             max = a
;
  
         p += 1;
  
         //Printing max of subarray
         //and shifting pointers
         //to next index.
         if (q == p && p != n) {
             cout <<max <<" " ;
             q++;
             p = ++t;
  
             if (q <n)
                 max = a[q];
         }
     }
}
  
//Driver Code
int main()
{
     int a[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
     int n = sizeof (a) /sizeof (a[0]);
     int K = 3;
  
     printKMax(a, n, K);
  
     return 0;
}

Java

//Java program to find the maximum for each
//and every contiguous subarray of size K
import java.util.*;
  
class GFG{
   
//Function to find the maximum for each
//and every contiguous subarray of size k
static void printKMax( int a[], int n, int k)
{
     //If k = 1, print all elements
     if (k == 1 ) {
         for ( int i = 0 ; i <n; i += 1 )
             System.out.print(a[i]+ " " );
         return ;
     }
   
     //Using p and q as variable pointers
     //where p iterates through the subarray
     //and q marks end of the subarray.
     int p = 0 , q = k - 1 , t = p, max = a[k - 1 ];
   
     //Iterating through subarray.
     while (q <= n - 1 ) {
   
         //Finding max
         //from the subarray.
         if (a
> max)
             max = a
;
   
         p += 1 ;
   
         //Printing max of subarray
         //and shifting pointers
         //to next index.
         if (q == p && p != n) {
             System.out.print(max+ " " );
             q++;
             p = ++t;
   
             if (q <n)
                 max = a[q];
         }
     }
}
   
//Driver Code
public static void main(String[] args)
{
     int a[] = { 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 };
     int n = a.length;
     int K = 3 ;
   
     printKMax(a, n, K);
}
}
  
//This code is contributed by 29AjayKumar

Python3

# Python3 program to find the maximum for each
# and every contiguous subarray of size K
  
# Function to find the maximum for each
# and every contiguous subarray of size k
def printKMax(a, n, k):
      
     # If k = 1, prall elements
     if (k = = 1 ):
         for i in range (n):
             print (a[i], end = " " );
         return ;
          
     # Using p and q as variable pointers
     # where p iterates through the subarray
     # and q marks end of the subarray.
     p = 0 ;
     q = k - 1 ;
     t = p;
     max = a[k - 1 ];
  
     # Iterating through subarray.
     while (q <= n - 1 ):
  
         # Finding max
         # from the subarray.
         if (a
> max ):
             max = a
;
         p + = 1 ;
  
         # Printing max of subarray
         # and shifting pointers
         # to next index.
         if (q = = p and p ! = n):
             print ( max , end = " " );
             q + = 1 ;
             p = t + 1 ;
             t = p;
  
             if (q <n):
                 max = a[q];
  
# Driver Code
if __name__ = = '__main__' :
     a = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ];
     n = len (a);
     K = 3 ;
  
     printKMax(a, n, K);
  
# This code is contributed by Princi Singh

C#

//C# program to find the maximum for each
//and every contiguous subarray of size K
using System;
  
class GFG{
    
//Function to find the maximum for each
//and every contiguous subarray of size k
static void printKMax( int []a, int n, int k)
{
     //If k = 1, print all elements
     if (k == 1) {
         for ( int i = 0; i <n; i += 1)
             Console.Write(a[i]+ " " );
         return ;
     }
    
     //Using p and q as variable pointers
     //where p iterates through the subarray
     //and q marks end of the subarray.
     int p = 0, q = k - 1, t = p, max = a[k - 1];
    
     //Iterating through subarray.
     while (q <= n - 1) {
    
         //Finding max
         //from the subarray.
         if (a
> max)
             max = a




;
    
         p += 1;
    
         //Printing max of subarray
         //and shifting pointers
         //to next index.
         if (q == p && p != n) {
             Console.Write(max+ " " );
             q++;
             p = ++t;
    
             if (q <n)
                 max = a[q];
         }
     }
}
    
//Driver Code
public static void Main(String[] args)
{
     int []a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
     int n = a.Length;
     int K = 3;
    
     printKMax(a, n, K);
}
}
   
//This code is contributed by Rajput-Ji

输出如下：

3 4 5 6 7 8 9 10

时间复杂度：O(N * k)

辅助空间复杂度：O(1)

---