# 最大滑動窗口（大小為 k 的所有子數組的最大值） > 原文： [https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/](https://www.geeksforgeeks.org/sliding-window-maximum-maximum-of-all-subarrays-of-size-k/) 給定一個數組和一個整數`k`，請找到每個相鄰的大小為`k`的子數組的最大值。 **示例**： ``` Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3 Output: 3 3 4 5 5 5 6 Explanation: Maximum of 1, 2, 3 is 3 Maximum of 2, 3, 1 is 3 Maximum of 3, 1, 4 is 4 Maximum of 1, 4, 5 is 5 Maximum of 4, 5, 2 is 5 Maximum of 5, 2, 3 is 5 Maximum of 2, 3, 6 is 6 Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4 Output: 10 10 10 15 15 90 90 Explanation: Maximum of first 4 elements is 10, similarly for next 4 elements (i.e from index 1 to 4) is 10, So the sequence generated is 10 10 10 15 15 90 90 ``` **方法 1**： 這是解決上述問題的簡單方法。 * **方法**： 這個想法非常基本，它運行一個嵌套循環，外部循環將標記長度為`k`的子數組的起始點，內部循環將從起始索引運行到`index + k`，從起始索引開始，將`k`個元素打印出來，并在這`k`個元素中顯示最大元素。 * **算法**： 1. 創建一個嵌套循環，即從起始索引到第`n – k`個元素的外循環。 內部循環將運行`k`次迭代。 2. 創建一個變量來存儲內部循環遍歷的`k`個元素的最大值。 3. 查找內循環遍歷的`k`個元素的最大值。 4. 在外循環的每次迭代中打印最大元素 * **實現**： ## 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); ????} } 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 method ????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 s? # 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\. ?> ``` **輸出**： ``` 3 4 5 6 7 8 9 10 ``` * **復雜度分析**： * **時間復雜度**： `O(N * K)`。 對于外循環的每次迭代，外循環運行`n-k + 1`次，內循環運行`k`次。 因此，時間復雜度為`O((n-k + 1) * k)`，也可以寫成`O(N * K)`。 * **空間復雜度**：`O(1)`。 不需要多余的空間。 **方法 2**： 此方法使用自平衡 BST 解決給定的問題。 * **方法**： 為了在子數組的`k`個元素中找到最大值，先前的方法使用遍歷元素的循環。 為了減少該時間，我們的想法是使用 [AVL 樹](https://www.geeksforgeeks.org/avl-tree-set-1-insertion/)，該樹返回`log n`時間中的最大元素。 因此，遍歷數組并將`k`個元素保留在 BST 中，并在每次迭代中打印最大值。 **AVL 樹**是一種合適的數據結構，因為在平均和最壞情況下查找，插入和刪除都需要`O(log n)`時間，其中`n`是操作之前樹中的節點數 。 * **算法**： 1. 創建一個自平衡 BST（AVL 樹）以存儲和查找最大元素。 2. 從頭到尾遍歷整個數組。 3. 將元素插入 AVL 樹中。 4. 如果循環計數器或大于或等于`k`，則從 BST 中刪除第`i-k`個元素 5. 打印 BST 的最大元素。 * **實現**： ``` // 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;? } ``` **輸出**： ``` 10 10 10 15 15 90 90 ``` * **復雜度分析**： * **時間復雜度**：`O(N * Log k)`。 插入，刪除和搜索在 AVL 樹中花費`log k`的時間。 因此，總體時間復雜度為`O(N * Log k)` * **空間復雜度**：`O(k)`。 在 BST 中存儲`k`個元素所需的空間為`O(k)`。 **方法 3：** 此方法使用`Deque`解決上述問題。 * **方法**： 創建容量為`k`的[雙端隊列](https://www.geeksforgeeks.org/deque-set-1-introduction-applications/)，`Qi`，該存儲僅存儲`k`個元素的當前窗口的有用元素。 如果一個元素在當前窗口中并且比當前窗口左側其他元素大，則該元素很有用。 逐一處理所有數組元素，并保持`Qi`包含當前窗口的有用元素，并且這些有用元素將按排序的順序進行維護。`Qi`前面的元素是最大的，而`Qi`后面的元素是當前窗口的最小元素。 感謝 [Aashish](https://www.geeksforgeeks.org/maximum-of-all-subarrays-of-size-k/#comment-10874) 提出了此方法。 * **Dry run of the above approach:**  * **算法**： 1. 創建一個雙端隊列以存儲`k`個元素。 2. 運行循環并將雙端`k`個元素插入雙端隊列。 如果在隊列后面的元素小于當前元素，則在插入元素時刪除所有那些元素，然后插入該元素。 3. 現在，運行從`k`到數組末尾的循環。 4. 打印數組的前部元素 5. 如果元素不在當前窗口中，請從隊列的最前面刪除該元素。 6. 將下一個元素插入雙端隊列。 如果在隊列后面的元素小于當前元素，則在插入元素時刪除所有那些元素，然后插入該元素。 7. 打印最后一個窗口的最大元素。 * **實現**： ## C++ ``` #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()]) ????????????Qi.pop_back(); // Remove from rear ????????// 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) ????????????Qi.pop_front(); // Remove from front of queue ????????// 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 program to test above functions 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()]) ????????????????Qi.removeLast(); // Remove from rear ????????????// 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 program to test above functions ????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 programm to test above fumctions 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.IndexOf(0)]) ????????????????Qi.RemoveAt(Qi.Count-1); // Remove from rear ????????????// 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 ``` **輸出**： ``` 78 90 90 90 89 ``` * **復雜度分析**： * **時間復雜度**：`O(n)`。 乍一看似乎不止`O(n)`。 可以看出，數組的每個元素最多只能添加和刪除一次。 因此共有`2n`次操作。 * **輔助空間**：`O(k)`。 存儲在出隊中的元素占據`O(k)`空間。 * 下面是此問題的擴展： [所有大小為`k`的子數組的最小和最大元素的總和。](https://www.geeksforgeeks.org/sum-minimum-maximum-elements-subarrays-size-k/) **方法 4**： 該方法使用最大堆解決上述問題。 * **方法**： 在上述方法中，其中之一是使用 AVL 樹。 該方法與該方法非常相似。 區別在于，此方法將使用最大堆而不是使用 AVL 樹。 當前窗口的元素將存儲在“最大堆”中，并且最大元素或根將在每次迭代中打印。 **最大堆**是一種合適的數據結構，因為它可以對其中的最小和最大元素進行恒定時間的檢索和對數時間去除，即找到恒定的最大元素并進行插入需要花費恒定的時間 刪除操作需要花費 n 倍的時間。 * **算法**： 1. 選擇前`k`個元素并創建大小為`k`的最大堆。 2. 執行建堆并打印根元素。 3. 存儲數組中的下一個和最后一個元素 4. 從`k – 1`到`n`運行循環 * 用從窗口中移出的新元素替換從窗口中移出的元素的值。 * 執行建堆。 * 打印堆的根。 * **實現**： ## Python3 ``` # Python program to find the maximum for? # each and every contiguous subarray of # size k? import heapq # Method to find the maximum for each # and every contiguous subarray of s? # of size k def max_of_all_in_k(arr, n): ????i = 0 ????j = k-1 ????# Create the heap and heapify ????heap = arr[i:j + 1] ????heapq._heapify_max(heap) ????# Print the maximum element from? ????# the first window of size k ????print(heap[0], end =" ") ????last = arr[i] ????i+= 1 ????j+= 1 ????nexts = arr[j] ????# For every remaining element ????while j < n: ????????# Add the next element of the window ????????heap[heap.index(last)] = nexts ????????# Heapify to get the maximum? ????????# of the current window ????????heapq._heapify_max(heap) ????????# Print the current maximum ????????print(heap[0], end =" ") ????????last = arr[i] ????????i+= 1 ????????j+= 1 ????????if j < n: ????????????nexts = arr[j] # Driver Function n, k = 10, 3 arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] max_of_all_in_k(arr, n) ``` **輸出**： ``` 3 4 5 6 7 8 9 10 ``` * **復雜度分析**： * **時間復雜度**： `O(n * k)`。 步驟 4（a）的時間復雜度為`O(k)`，步驟 4（b）的復雜度為`O(Log(k))`，并且它處于運行`n – k + 1`次的循環中。 因此，完整算法的時間復雜度為`O((k + Log(k)) * n)`，即`O(n * k)`。 * **空間復雜度**：`O(k)`。 使用將元素存儲在堆`O(k)`空間中。 如果您發現上述代碼/算法有誤，請寫評論，或者找到其他解決相同問題的方法。