窗口最大值数组

生成窗口最大值数组

有一个整型数组arr和一个大小为w的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

例如，数组为[4,3,5,4,3,3,6,7]，窗口大小为3时：

[4 3 5] 4 3 3 6 7 窗口中最大值为5

4 [3 5 4] 3 3 6 7 窗口中最大值为5

4 3 [5 4 3] 3 6 7 窗口中最大值为5

4 3 5 [4 3 3] 6 7 窗口中最大值为4

4 3 5 4 [3 3 6] 7 窗口中最大值为6

4 3 5 4 3 [3 6 7] 窗口中最大值为7

结果应该返回[5,5,5,4,6,7]。

简单代码如下：

 1 /**
 2  * 简单方法
 3  * 狗剩的美丽家园
 4  */
 5 #include <iostream>
 6 #include <vector>
 7 using namespace std;
 8 
 9 class Solution {
10 public:
11     int getMax(const int A[], int size) {
12         int max_num = A[0];
13         for (int i = 0; i < size; i++) {
14             if (A[i] > max_num) {
15                 max_num = A[i];
16             }
17         }
18         return max_num;
19     }
20 
21     vector<int> maxInWindows(const int A[], int n, int size) {
22         vector<int> result;
23         for (int i = 0; i < n - size + 1; i++) {
24             int num = getMax(A + i, size);
25             result.push_back(num);
26         }
27         return result;
28     }
29 };
30 int main() {
31     Solution s;
32     const int A[] = {2,3,4,2,6,2,5,1};
33     int size = 3;
34     int n = sizeof(A) / sizeof(A[0]);
35     vector<int> res;
36     res = s.maxInWindows(A, n, size);
37     for (int i = 0; i < res.size(); i++) {
38         cout << res[i] << ",";
39     }
40 }

时间复杂度为 O(N)的解法如下：

 1 /**
 2  * 双端队列
 3  * 狗剩的美丽家园
 4 **/
 5 
 6 #include <iostream>
 7 #include <vector>
 8 #include <deque>
 9 using namespace std;
10 
11 vector<int> maxInWindows(int A[], int n, int size) {
12     deque<int> Q;
13     vector<int> result;
14     for (int i = 0; i < n; i++) {
15         //当前元素大于等于队尾，队尾出队
16         while (!Q.empty() && A[Q.back()] <= A[i]) {
17             Q.pop_back();
18         }
19         Q.push_back(i);
20 
21         //窗口范围大于size，队头出队列
22         if (Q.front() == i - size) {
23             Q.pop_front();
24         }
25         if (i >= size - 1) {
26             result.push_back(A[Q.front()]);
27         }
28     }
29     return result;
30 }
31 
32 int main() {
33     int A[] = {2,3,4,2,6,2,5,1};
34     int size = 3;
35     int n = sizeof(A) / sizeof(A[0]);
36     vector<int> res;
37     res = maxInWindows(A, n, size);
38     for (int i = 0; i < res.size(); i++) {
39         cout << res[i] << ",";
40     }
41 }