算法设计（最大滑动窗口-大小为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

【算法设计（最大滑动窗口-大小为k的所有子数组的最大值 S2）】方法：为了在较小的空间复杂度中解决此问题, 我们可以使用二指针技术.

第一个变量指针遍历子数组并从给定大小中找到最大元素?
第二个变量指针标记第一个变量指针的结束索引, 即第(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# 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

输出如下：