[LeetCode 239] Sliding Window Maximum

作者 Shilei Tian 日期 2017-07-12
[LeetCode 239] Sliding Window Maximum

题目要求

Given an array nums, there is a sliding window of size k which is moving from the very left of the array to the very right. You can only see the k numbers in the window. Each time the sliding window moves right by one position.

For example,
Given nums = [1,3,-1,-3,5,3,6,7], and k = 3.

Window position Max
--------------- -----
[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

Therefore, return the max sliding window as [3,3,5,5,6,7].

Note:
You may assume k is always valid, ie: 1 ≤ k ≤ input array’s size for non-empty array.

Follow up:
Could you solve it in linear time?

解题思路

这道题目要求很简单,有一个大小为 k 的滑动窗口,从左向右滑动,求出每次窗口中最大值。我们可以很简单的想到一种时间复杂度为 O(kn) 的算法,即每次找窗口中的最大值。

进一步想,滑动窗口每次只删除左边的元素,加入右边的元素,如果我们能够将窗口中的元素维护一个 multiset,那么就可以得到一个时间复杂度为 O(nlogk) 的算法,对应的代码如下:

class Solution {
struct Window {
multiset<int, greater<int>> orderedData;
deque<int> data;
size_t capacity;
Window(size_t k) : capacity(k){}
int getMax() {
return *orderedData.begin();
}
void insert(int val) {
if (data.size() >= capacity) {
orderedData.erase(orderedData.equal_range(data.front()).first);
data.pop_front();
}
orderedData.insert(val);
data.push_back(val);
}
};
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
if (nums.empty() || nums.size() < k || k == 0) {
return ret;
}
Window window(k);
for (size_t i = 0; i < k; ++i) {
window.insert(nums[i]);
}
ret.push_back(window.getMax());
for (size_t i = k; i < nums.size(); ++i) {
window.insert(nums[i]);
ret.push_back(window.getMax());
}
return ret;
}
};

在 LeetCode 上面所有的 cases 运行完是需要 89ms,超过 22.39% 的人。

那么有没有更好的算法?或者说,有没有 O(n) 的算法呢?这里就要引入一种数据结构,叫做 Monotonic Queue,这种数据结构支持三个操作:push_backpop_frontget_top。其中最后一个 get_top 的操作可以对应最大值或最小值。由于它只对头尾进行操作,所以基础的结构可以用 deque 来实现。

我们假设用 D 来表示一个 deque,它的元素是一个 pair<size_t, val_type>D 的一个重要特性是:它的元素总是按照元素值的顺序排列的(由大到小或由小到大)。这里我们需要找到最大值,所以它里面的元素就是由大到小排列的,最大的元素就是队头元素。

假设我们现在扫描到第 i 个元素,根据上面的特性,如果我们想要将 nums[i] 加进去,那么所有小于 a[i] 的元素都要弹出。除此之外,因为我们滑动窗口/队列的大小有限制,如果 D 的队头元素对应的下标与当前下标的差刚好为 k,那么我们需要弹出队头元素。

根据上面的描述,我们就能为本题设计出下面的答案来:

class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> ret;
deque<pair<size_t, int>> dq;
for (size_t i = 0; i < nums.size(); ++i) {
if (!dq.empty() && dq.front().first == i - k) {
dq.pop_front();
}
while (!dq.empty() && dq.back().second < nums[i]) {
dq.pop_back();
}
dq.push_back({i, nums[i]});
if (i >= k - 1) {
ret.push_back(dq.front().second);
}
}
return ret;
}
};

时间复杂度为 O(n),运行时间为 66ms,超过 78.19% 的人。