- 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 | For example, |

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:

- How about using a data structure such as deque (double-ended queue)?
- The queue size need not be the same as the window’s size.
- 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 | class Solution { |

我的代码实现：

1 | class Solution { |

方法二：

对方法一代码进行了优化

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 | class Solution { |

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

附注：

牛客网

1 | class Solution { |

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 | class Monoqueue |

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 | class Solution { |

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

A clear solution using deque (C++)

1 | class Solution { |

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

3 C++ Solutions

- O(NlogK)

1 | vector<int> maxSlidingWindow(vector<int>& nums, int k) { |

- O(NlogN)

1 | vector<int> maxSlidingWindow(vector<int>& nums, int k) { |

- O(N)

1 | vector<int> maxSlidingWindow(vector<int>& nums, int k) { |

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

A concise solution using deque

1 | vector<int> maxSlidingWindow(vector<int>& nums, int k) { |

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:

- Pop (from the end) indexes of smaller elements (they’ll be useless).
- Append the current index.
- Pop (from the front) the index i - k, if it’s still in the deque (it falls out of the window).
- 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 | def max_sliding_window(nums, k) |

Python

1 | def maxSlidingWindow(self, nums, k): |

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

1 | out += nums[d[0]], |

27ms, 31.12%, October 14, 2016

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

1 | public class Solution { |