• 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.

Note:

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

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.

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

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

You can also view more solution on Github

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

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.

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).

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

A clear solution using deque (C++)

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

3 C++ Solutions

1. O(NlogK)
1. O(NlogN)
1. O(N)

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

A concise solution using deque

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.

Python

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

27ms, 31.12%, October 14, 2016

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