[LeetCode] 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 = <code>[1,3,-1,-3,5,3,6,7]</code>, and k = 3.

Therefore, return the max sliding window as <code>[3,3,5,5,6,7]</code>.

Note: 

You may assume k is always valid, 1 ≤ k ≤ input array's size.

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.

這道題給定了一個數組，還給了一個視窗大小k，讓我們每次向右滑動一個數字，每次傳回視窗内的數字的最大值，而且要求我們代碼的時間複雜度為O(n)。提示我們要用雙向隊列deque來解題，并提示我們視窗中隻留下有用的值，沒用的全移除掉。果然Hard的題目我就是不會做，網上看到了别人的解法才明白，解法又巧妙有簡潔，膜拜啊。大概思路是用雙向隊列儲存數字的下标，周遊整個數組，如果此時隊列的首元素是i - k的話，表示此時視窗向右移了一步，則移除隊首元素。然後比較隊尾元素和将要進來的值，如果小的話就都移除，然後此時我們把隊首元素加入結果中即可，參見代碼如下：