固定范围内最大值-布布扣-bubuko.com

Description

给你一个整数数组，有一个大小为k的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看见在滑动窗口中的k个数字。滑动窗口每次向右移动一位。请输出每个窗口中的最大值。

Input

输入包含三部分，数组的长度，数组中各元素，滑动窗口大小。例如：

1 3 -1 -3 5 3 6 7

Output

输出每个滑动窗口中元素的最大值，元素间用空格分隔，如：

[1 3 -1] -3 5 3 6 7 3

1 [3 -1 -3] 5 3 6 7 3

1 3 [-1 -3 5] 3 6 7 5

1 3 -1 [-3 5 3] 6 7 5

1 3 -1 -3 [5 3 6] 7 6

1 3 -1 -3 5 [3 6 7] 7

输出：3 3 5 5 6 7

Sample Input 1

8
1 3 -1 -3 5 3 6 7
3

Sample Output 1

3 3 5 5 6 7

Hint

若数组长度小于窗口值，或窗口值为0，则输出为空。

解题思路：

使用滑动窗口的思路来解题，从第一个数组元素开始往后遍历，将数组中的初始元素及其后面的K-1个元素放入vector容器中，最后找出

这K个数的最大值即可。

题解：

 1 #define _CRT_SECURE_NO_WARNINGS 1
 2 
 3 #include<iostream>
 4 #include<vector>
 5 
 6 using namespace std;
 7 
 8 //找出容器v中的最大值
 9 void find_max(vector<int> v,int k)
10 {
11     int max = v[0];
12     
13     for (int i = 0; i < k; i++)
14     {
15         if (v[i] > max)
16             max = v[i];
17     }
18     cout << max <<" ";
19 }
20 int main()
21 {
22     int n, arr[20],k;  
23     vector<int>v;
24     cin >> n;
25     for (int i = 0; i < n; i++)
26     {
27         cin >> arr[i];
28     }
29     cin >> k; //输入窗口的大小
30 
31     if ((n < k) || (k == 0))
32         return 0;
33 
34     for (int i = 0 , j = i+k; i < n-k+1; i++,j++)
35     {
36         for (int m = i; m < j; m++)
37         {
38             v.push_back(arr[m]);
39         }
40         find_max(v,k);
41         v.clear();  //每次找出最大值后清空容器V中的元素
42     }
43     return 0;
44 
45 }