AcWing 79. 滑动窗口的最大值
宋标 Lv5
  2022-08-18 02:30:48 2022-08-18 02:30    

题目

给定一个数组和滑动窗口的大小，请找出所有滑动窗口里的最大值。

例如，如果输入数组 及滑动窗口的大小 ，那么一共存在 个滑动窗口，它们的最大值分别为 。

注意：

  • 数据保证 大于 ，且 小于等于数组长度。

数据范围

数组长度 。

样例

输入：[2, 3, 4, 2, 6, 2, 5, 1] , k=3

输出: [4, 4, 6, 6, 6, 5]

题解

N方的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    vector<int> maxInWindows(vector<int>& nums, int k) {

        vector<int> ans;
        for (int i = k - 1, j = 0; i < nums.size(); ++ i, ++ j)
        {
            int t = -1e9;
            for (int p = j; p <= i; ++ p) t = max(t, nums[p]);
            ans.push_back(t);
        }

        return ans;
    }
};

N的做法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#define N 1010

class Solution {
public:

    int qe[N];
    int hh, tt;

    vector<int> maxInWindows(vector<int>& nums, int k) {
        vector<int> ans;
        for (int j = 0; j < nums.size(); ++ j)
        {
            while (tt > hh && nums[ qe[tt - 1] ] <= nums[j]) -- tt;
            while (tt > hh && qe[hh] <= j - k) ++ hh;
            qe[tt ++] = j;
            if (j >= k - 1) ans.push_back(nums[ qe[hh] ]);
        }

        return ans;
    }
};
 评论