给定一个数组和一个整数 K ，找到大小为k的每个相邻子阵列的最大值。
null
例如：
Input: arr[] = {1, 2, 3, 1, 4, 5, 2, 3, 6}, K = 3 Output: 3 3 4 5 5 5 6Explanation: Maximum of 1, 2, 3 is 3Maximum of 2, 3, 1 is 3Maximum of 3, 1, 4 is 4Maximum of 1, 4, 5 is 5Maximum of 4, 5, 2 is 5 Maximum of 5, 2, 3 is 5Maximum of 2, 3, 6 is 6Input: arr[] = {8, 5, 10, 7, 9, 4, 15, 12, 90, 13}, K = 4 Output: 10 10 10 15 15 90 90Explanation: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的子数组的起点，内循环将从起始索引运行到索引+k，从起始索引运行k个元素，并打印这些k个元素中的最大元素。
算法：
- 创建一个嵌套循环，即从起始索引到第n–k个元素的外部循环。内部循环将运行k次迭代。
- 创建一个变量来存储内部循环遍历的最大k个元素。
- 求内部循环遍历的k个元素的最大值。
- 打印外循环每次迭代的最大元素
实施：
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); } } // 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; } |
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 code 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 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. ?> |
Javascript
<script> // JavaScript 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 size k. function printKMax(arr,n,k) { let j, max; for (let i = 0; i <= n - k; i++) { max = arr[i]; for (j = 1; j < k; j++) { if (arr[i + j] > max) max = arr[i + j]; } document.write( max + " " ); } } // Driver code let arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 ]; let n =arr.length; let k = 3; printKMax(arr, n, k); // This code contributed by gauravrajput1 </script> |
输出
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个元素中找到最大值，前面的方法使用循环遍历元素。为了缩短这段时间，我们的想法是使用 平衡二叉树 返回log n time中的最大元素。所以，遍历数组，在BST中保留k个元素，并在每次迭代中打印最大值。 平衡二叉树 是一种合适的数据结构，因为在平均和最坏的情况下，查找、插入和删除都需要O（logn）时间，其中n是操作之前树中的节点数。
算法：
- 创建一个自平衡BST（AVL树）来存储和查找最大元素。
- 从头到尾遍历阵列。
- 在AVL树中插入元素。
- 如果循环计数器大于或等于k，则从BST中删除第i-k个元素
- 打印BST的最大元素。
实施：
C++14
// 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; } |
JAVA
// JAVA program to delete a node from AVL Tree import java.io.*; import java.util.*; class GFG { static ArrayList<Integer> findKMaxElement( int [] arr, int k, int n) { // creating the max heap ,to get max element always PriorityQueue<Integer> queue = new PriorityQueue<>( Collections.reverseOrder()); ArrayList<Integer> res = new ArrayList<>(); int i = 0 ; for (; i < k; i++) queue.add(arr[i]); // adding the maximum element among first k elements res.add(queue.peek()); // removing the first element of the array queue.remove(arr[ 0 ]); // iterarting for the next elements for (; i < n; i++) { // adding the new element in the window queue.add(arr[i]); // finding & adding the max element in the // current sliding window res.add(queue.peek()); // finally removing the first element from front // end of queue queue.remove(arr[i - k + 1 ]); } return res; // this code is Contributed by Pradeep Mondal P } // Driver Code public static void main(String[] args) { int arr[] = { 8 , 5 , 10 , 7 , 9 , 4 , 15 , 12 , 90 , 13 }; int k = 4 , n = arr.length; List<Integer> res = findKMaxElement(arr, k, n); for ( int x : res) System.out.print(x + " " ); } } |
Javascript
<script> // JAVAscript program to delete a node from AVL Tree function findKMaxElement(arr, k, n) { // creating the max heap ,to get max element always let queue = []; let res = []; let i = 0; for (; i < k; i++) queue.push(arr[i]); queue.sort( function (a,b){ return b-a;}); // adding the maximum element among first k elements res.push(queue[0]); // removing the first element of the array queue.splice(arr[0],1); // iterarting for the next elements for (; i < n; i++) { // adding the new element in the window queue.push(arr[i]); queue.sort( function (a,b){ return b-a;}); // finding & adding the max element in the // current sliding window res.push(queue[0]); // finally removing the first element from front // end of queue queue.splice(arr[i - k + 1],1); } return res; // this code is Contributed by Pradeep Mondal P } // Driver Code let arr = [ 8, 5, 10, 7, 9, 4, 15, 12, 90, 13]; let k = 4, n = arr.length; let res = findKMaxElement(arr, k, n); for (let x of res) document.write(x + " " ); // This code is contributed by avanitrachhadiya2155 </script> |
C#
// C# program to delete a node from AVL Tree using System; using System.Collections.Generic; public class GFG { static List< int > findKMaxElement( int [] arr, int k, int n) { // creating the max heap ,to get max element always List< int > queue = new List< int >(); List< int > res = new List< int >(); int i = 0; for (; i < k; i++) queue.Add(arr[i]); queue.Sort(); queue.Reverse(); // adding the maximum element among first k elements res.Add(queue[0]); // removing the first element of the array queue.Remove(arr[0]); // iterarting for the next elements for (; i < n; i++) { // adding the new element in the window queue.Add(arr[i]); queue.Sort(); queue.Reverse(); // finding & adding the max element in the // current sliding window res.Add(queue[0]); // finally removing the first element from front // end of queue queue.Remove(arr[i - k + 1]); } return res; // this code is Contributed by Pradeep Mondal P } // Driver Code public static void Main(String[] args) { int [] arr = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 }; int k = 4, n = arr.Length; List< int > res = findKMaxElement(arr, k, n); foreach ( int x in res) Console.Write(x + " " ); } } // This code is contributed by umadevi9616 |
输出
10 10 10 15 15 90 90
复杂性分析：
- 时间复杂性 : O（N*logk） . 在AVL树中，插入、删除和搜索需要花费logk时间。所以总的时间复杂度是O（N*logk）
- 空间复杂性： 好的。 在BST中存储k个元素所需的空间是O（k）。
方法3： 该方法使用Deque来解决上述问题
方法： 创建一个 德克 , 气 容量为k，仅存储当前k个元素窗口中的有用元素。如果某个元素位于当前窗口中，并且大于当前窗口中该元素右侧的所有其他元素，则该元素非常有用。逐个处理所有数组元素并维护 气 以包含当前窗口的有用元素，并且这些有用元素按排序顺序进行维护。前面的元素 气 是最大的一个，位于车辆后部/后部 气 是当前窗口的最小值。幸亏 阿希什 感谢你提出这种方法。
上述方法的试运行：
![图片[1]-滑动窗口最大值（大小为k的所有子阵列的最大值）-yiteyi-C++库](https://www.yiteyi.com/wp-content/uploads/geeks/20190626/geeks_SlidingWindowMaximum.png)
算法：
- 创建一个deque来存储k个元素。
- 运行一个循环并在deque中插入前k个元素。在插入元素之前，检查队列后面的元素是否小于当前元素，如果小于当前元素，则从队列后面移除元素，直到队列中剩余的所有元素都大于当前元素。然后将当前元素插入到deque的后面。
- 现在，从k到数组的末尾运行一个循环。
- 打印deque的前元素。
- 如果元素不在当前窗口中，请从队列前面移除它们。
- 在deque中插入下一个元素。在插入元素之前，检查队列后面的元素是否小于当前元素，如果小于当前元素，则从队列后面移除元素，直到队列中剩余的所有元素都大于当前元素。然后将当前元素插入到deque的后面。
- 打印最后一个窗口的最大元素。
实施：
C++
// CPP program for the above approach #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()]) // Remove from rear Qi.pop_back(); // 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) // Remove from front of queue Qi.pop_front(); // 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 code 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()]) // Remove from rear Qi.removeLast(); // 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 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 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 code 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[Qi.Count-1]]) // Remove from rear Qi.RemoveAt(Qi.Count-1); // 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）空间。
以下是此问题的扩展： 大小为k的所有子阵列的最小和最大元素之和。
方法4 : 此方法是对两个堆栈的队列实现的修改：
算法：
- 在推动元素的同时，我们不断地推进堆栈2。堆栈2的最大值始终是堆栈2顶部元素的最大值。
- 在弹出时，我们总是从堆栈1弹出，如果堆栈1为空，那么我们将把堆栈2的每个元素推送到堆栈1，并更新最大值
- 堆栈的队列实现遵循上述两个步骤
- 现在，为了找到整个队列的最大值（与两个堆栈相同），我们将取两个堆栈最大值的顶部元素；因此，这是整个队列的最大值。
- 现在，这项技术可以用来滑动窗口并获得最大值。
- 按1个索引滑动窗口时，删除最后一个索引，插入新的索引，然后取两个堆栈的最大值
实施
C++
#include <bits/stdc++.h> using namespace std; struct node{ int data; int maximum; }; // it is a modification in the way of implementation of queue using two stack void insert(stack<node> &s2 , int val) { //inserting the element in s2 node other; other.data=val; if (s2.empty()) other.maximum=val; else { node front=s2.top(); //updating maximum in that stack push it other.maximum=max(val,front.maximum); } s2.push(other); return ; } void delete (stack<node> &s1 ,stack<node> &s2 ) { //if s1 is not empty directly pop //else we have to push all element from s2 and thatn pop from s1 //while pushing from s2 to s1 update maximum variable in s1 if (s1.size()) s1.pop(); else { while (!s2.empty()) { node val=s2.top(); insert(s1,val.data); s2.pop(); } s1.pop(); } } int get_max(stack<node> &s1 ,stack<node> &s2 ) { // the maximum of both stack will be the maximum of overall window int ans=-1; if (s1.size()) ans=max(ans,s1.top().maximum); if (s2.size()) ans=max(ans,s2.top().maximum); return ans; } vector< int > slidingMaximum( int a[], int b, int n) { //s2 for push //s1 for pop vector< int >ans; stack<node>s1,s2; //shifting all value except the last one if first window for ( int i=0;i<b-1;i++) insert(s2,a[i]); for ( int i=0;i<=n-b;i++) { //removing the last element of previous window as window has shift by one if (i-1>=0) delete (s1,s2); //adding the new element to the window as the window is shift by one insert(s2,a[i+b-1]); ans.push_back(get_max(s1,s2)); } return ans; } int main() { int arr[] = { 8, 5, 10, 7, 9, 4, 15, 12, 90, 13 }; int n = sizeof (arr) / sizeof (arr[0]); int k = 4; vector< int > ans=slidingMaximum(arr,k,n); for ( auto x:ans) cout<<x<< " " ; return 0; } |
输出
78 90 90 90 89
复杂性分析：
- 时间复杂性 ：O（N）：这是因为每个元素只会有两种类型的push和pop；因此，时间复杂度是线性的。
- 空间复杂性 ：O（K）：这是因为在任何时刻，两个堆栈的堆栈大小之和都将恰好等于K，因为每次我们只弹出一个元素，并按下一个元素。
方法5： 该方法使用最大堆来解决上述问题。
方法： 在上述方法中，其中一种是使用AVL树。这种方法与那种方法非常相似。不同之处在于，这种方法不使用AVL树，而是使用Max Heap。当前窗口的元素将存储在最大堆中，并且在每次迭代中打印最大元素或根。 最大堆 是一种合适的数据结构，因为它提供了对其中最小和最大元素的恒定时间检索和对数时间删除，即查找最大元素需要恒定时间，插入和删除需要对数n时间。
算法：
- 选择前k个元素并创建一个最大大小为k的堆。
- 执行heapify并打印根元素。
- 存储数组中的下一个和最后一个元素
- 从k–1到n运行一个循环
- 将从窗口中获取的元素值替换为进入窗口的新元素。
- 表演heapify。
- 打印堆的根。
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
