239. Sliding Window Maximum

  • 32.0%

https://leetcode.com/problems/sliding-window-maximum/#/description

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.

1
2
3
4
5
6
7
8
9
10
11
12
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?

Hint:

  1. How about using a data structure such as deque (double-ended queue)?
  2. The queue size need not be the same as the window’s size.
  3. Remove redundant elements and the queue should store only elements that need to be considered.

剑指offer 65

方法一:

使用剑指offer 方法,使用了一个deque,双端开口的队列

deque的方法有pop_back, pop_front, front, back.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
int n = nums.size();
if(k<=0 || n<1 || k>n)
return res;
deque<int> dq;
for(int i=0; i<k; i++){
while(!dq.empty() && nums[i]>nums[dq.back()])
dq.pop_back();
dq.push_back(i);
}

for(int i=k; i<n; i++){
res.push_back(nums[dq.front()]);
while(!dq.empty() && nums[dq.back()]<nums[i])
dq.pop_back();
if(!dq.empty() && (i-dq.front())>=k) //用if而不是while,因为每次进来一个最多只需要pop一个
dq.pop_front();
dq.push_back(i);
}
res.push_back(nums[dq.front()]);
return res;
}
};

我的代码实现:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> res;
int n = nums.size();
if(n==0 || k<=0 || n<k) return res;
deque<int> dq;
for(int i=0; i<k; i++){
while(!dq.empty() && nums[dq.back()]<=nums[i])
dq.pop_back();
dq.push_back(i);
}
for(int i=k; i<n; i++){
res.push_back(nums[dq.front()]);
while(!dq.empty() && nums[dq.back()]<=nums[i])
dq.pop_back();
// 要检查dq是否为空
if(!dq.empty() && dq.front()+k<=i)
dq.pop_front();
dq.push_back(i);
}
if(!dq.empty())
res.push_back(nums[dq.front()]);
return res;
}
};

方法二:

对方法一代码进行了优化

Clean C++ O(n) solution using a deque

The data structure used is know as Monotonic Queue. Click here for more information.

You can also view more solution on Github

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> dq;
vector<int> ans;
for (int i=0; i<nums.size(); i++) {
if (!dq.empty() && dq.front() == i-k) dq.pop_front();
while (!dq.empty() && nums[dq.back()] < nums[i])
dq.pop_back();
dq.push_back(i);
if (i>=k-1) ans.push_back(nums[dq.front()]);
}
return ans;
}
};

https://discuss.leetcode.com/topic/19067/clean-c-o-n-solution-using-a-deque

附注:

牛客网

https://www.nowcoder.com/practice/1624bc35a45c42c0bc17d17fa0cba788?tpId=13&tqId=11217&tPage=4&rp=4&ru=/ta/coding-interviews&qru=/ta/coding-interviews/question-ranking

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size)
{
deque<int> dq;
vector<int> res;
for(int i=0; i<num.size(); i++){
if(!dq.empty() && (i-dq.front())>=size)
dq.pop_front();
while(!dq.empty() && num[i]>=num[dq.back()])
dq.pop_back();
dq.push_back(i);
if(i>=size-1) res.push_back(num[dq.front()]);
}
return res;
}
};

https://discuss.leetcode.com/topic/19297/this-is-a-typical-monotonic-queue-problem

This is a typical monotonic queue problem

Sliding window minimum/maximum = monotonic queue. I smelled the solution just when I read the title.

This is essentially same idea as others’ deque solution, but this is much more standardized and modulized. If you ever need to use it in your real product, this code is definitely more preferable.

What does Monoqueue do here:

It has three basic options:

push: push an element into the queue; O (1) (amortized)

pop: pop an element out of the queue; O(1) (pop = remove, it can’t report this element)

max: report the max element in queue;O(1)

It takes only O(n) time to process a N-size sliding window minimum/maximum problem.

Note: different from a priority queue (which takes O(nlogk) to solve this problem), it doesn’t pop the max element: It pops the first element (in original order) in queue.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Monoqueue
{
deque<pair<int, int>> m_deque; //pair.first: the actual value,
//pair.second: how many elements were deleted between it and the one before it.
public:
void push(int val)
{
int count = 0;
while(!m_deque.empty() && m_deque.back().first < val)
{
count += m_deque.back().second + 1;
m_deque.pop_back();
}
m_deque.emplace_back(val, count);
};
int max()
{
return m_deque.front().first;
}
void pop ()
{
if (m_deque.front().second > 0)
{
m_deque.front().second --;
return;
}
m_deque.pop_front();
}
};
struct Solution {
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> results;
Monoqueue mq;
k = min(k, (int)nums.size());
int i = 0;
for (;i < k - 1; ++i) //push first k - 1 numbers;
{
mq.push(nums[i]);
}
for (; i < nums.size(); ++i)
{
mq.push(nums[i]); // push a new element to queue;
results.push_back(mq.max()); // report the current max in queue;
mq.pop(); // pop first element in queue;
}
return results;
}
};

https://discuss.leetcode.com/topic/19199/my-c-o-n-deque-based-solution-with-explanation

My C++ O(n) deque based solution with explanation

The basic idea is to use a deque (buffer) to save all currently potential “maximum” elements (i.e. the element in the current k-element window [i-k+1, i], and it is larger than the elements after itself). So for each i, we first pop up the elements that are no larger than nums[i] from buffer until we find one that is larger than nums[i] or the buffer is empty since those elements will be covered by nums[i] and can not be a maximum of any k-element window. Then we put nums[i] in the buffer. If i>=k-1, we need to ouput the maximum for window [i-k+1, i], which is the front element of buffer. At last, we will check if the front element is nums[i-k+1], if so, we have to pop it up since it will be out of the window [i-k+2, i+1] in the next iteration. Since all the elements will be pushed into/ popped out of the buffer only once, so the time complexity is O(N).

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

for(auto i=0; i<nums.size();++i)
{
while(!buffer.empty() && nums[i]>=nums[buffer.back()]) buffer.pop_back();
buffer.push_back(i);

if(i>=k-1) res.push_back(nums[buffer.front()]);
if(buffer.front()<= i-k + 1) buffer.pop_front();
}
return res;
}

https://discuss.leetcode.com/topic/23020/a-clear-solution-using-deque-c

A clear solution using deque (C++)

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

deque<int> q;
vector<int> maxs;
if(nums.empty()||k<=0) return maxs;

for(int i=0;i<nums.size();i++){
while(!q.empty()&&nums[q.back()]<=nums[i])
q.pop_back();
q.push_back(i);
if(q.front()<=i-k) q.pop_front();

if(i>=k-1) maxs.push_back(nums[q.front()]);
}
return maxs;
}
};

https://discuss.leetcode.com/topic/19099/3-c-solutions

3 C++ Solutions

  1. O(NlogK)
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
if (k == 0) return result;
multiset<int> w;
for (int i = 0, n = (int)nums.size(); i < n; i++) {
if (i >= k)
w.erase(w.find(nums[i-k]));
w.insert(nums[i]);
if (i >= k-1)
result.push_back(*w.rbegin());
}
return result;
}
  1. O(NlogN)
1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
if (k == 0) return result;
priority_queue<pair<int, int>> w;
for (int i = 0, n = (int)nums.size(); i < n; i++) {
while (!w.empty() && w.top().second <= i-k)
w.pop();
w.push(make_pair(nums[i],i));
if (i >= k-1)
result.push_back(w.top().first);
}
return result;
}
  1. O(N)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int> result;
if (k == 0) return result;
deque<int> w;
for (int i = 0, n = (int)nums.size(); i < n; i++) {
while (!w.empty() && w.front() <= i-k)
w.pop_front();
while (!w.empty() && nums[w.back()] <= nums[i])
w.pop_back();
w.push_back(i);
if (i >= k-1)
result.push_back(nums[w.front()]);
}
return result;
}

https://discuss.leetcode.com/topic/31686/a-concise-solution-using-deque

A concise solution using deque

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
if (k <= 0) return {};

vector<int> ans(nums.size() - k + 1);
deque<int> dq;
for (int i = 0; i < nums.size(); ++i) {
// delete those nodes whose value less than the current value
while (!dq.empty() && nums[i] > nums[dq.back()]) dq.pop_back();
dq.push_back(i);
// delete the node pass the start of the window
if (i - dq.front() + 1 > k) dq.pop_front();
// assign result value
if (i >= k - 1) ans[i - k + 1] = nums[dq.front()];
}

return ans;
}

https://discuss.leetcode.com/topic/19059/9-lines-ruby-11-lines-python-o-n

9 lines Ruby, 11 lines Python, O(n)

Keep indexes of good candidates in deque d. The indexes in d are from the current window, they’re increasing, and their corresponding nums are decreasing. Then the first deque element is the index of the largest window value.

For each index i:

  1. Pop (from the end) indexes of smaller elements (they’ll be useless).
  2. Append the current index.
  3. Pop (from the front) the index i - k, if it’s still in the deque (it falls out of the window).
  4. If our window has reached size k, append the current window maximum to the output.

Ruby

Apparently Ruby doesn’t have a deque, so I simulate one with an array, where s tells the start index of the queue in the array.

1
2
3
4
5
6
7
8
9
10
11
def max_sliding_window(nums, k)
d, s = [], 0
out = []
nums.each_index{ |i|
d.pop while d[s] && nums[d[-1]] < nums[i]
d << i
s += 1 if d[s] == i - k
out << nums[d[s]] if i >= k - 1
}
out
end

Python

1
2
3
4
5
6
7
8
9
10
11
12
def maxSlidingWindow(self, nums, k):
d = collections.deque()
out = []
for i, n in enumerate(nums):
while d and nums[d[-1]] < n:
d.pop()
d += i,
if d[0] == i - k:
d.popleft()
if i >= k - 1:
out += nums[d[0]],
return out

Last three lines could be this, but for relatively large k it would waste space:

1
2
out += nums[d[0]],
return out[k-1:]

27ms, 31.12%, October 14, 2016

https://discuss.leetcode.com/topic/19055/java-o-n-solution-using-deque-with-explanation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums==null || k<=0)
return new int[0];

int n = nums.length;
int[] r = new int[n-k+1];
int ri = 0;
Deque<Integer> q = new ArrayDeque<>();
for(int i=0; i<nums.length; i++){
while(!q.isEmpty() && q.peek() < i-k+1)
q.poll();
while(!q.isEmpty()&&nums[q.peekLast()]<nums[i])
q.pollLast();
q.offer(i);
if(i>=k-1)
r[ri++] = nums[q.peek()];
}
return r;
}
}
谢谢你,可爱的朋友。