239. Sliding Window Maximum

Link

難易度 : Hard

又來了一題Hard的題目，題目給一個整數陣列nums與一個窗口長度k，窗口從左向右滑動，要求依序紀錄窗口移動的過程中在窗口內的最大值

題目的關鍵在於每次窗口滑動時，左邊元素會離開、右邊元素會進來，那要怎麼在滑動的過程中都得知當前窗口的最大值了?

直接兩個for迴圈可不可以呢?當然可以，只是很遺憾地在這題裡會直接timeout。

把問題核心再描述的精準一點

1. 要如何再一減一增的過程記錄下當前的最大值
2. 每次都能不用重新搜尋就能得知最大值是多少

於是這邊我使用了deque來操作滑動的過程中記錄最大值
關鍵的思路是

(這邊我的deque是做成降序，也就是first就是max)

1. 這個deque內的元素需要排序，升降無所謂，只要讓最大值保持在deque的頭或尾可以直接看到即可
2. 當元素離開的時候，我要知道這個元素是不是當前最大的值
   A. 如果離開的元素恰巧等於最大值，那麼deque需要將這個元素poll移除
3. 當有元素newV進來時，需要對其排序，並且在比較結束後push進deque中
   A. 若是newV比deque中最小的元素(last)還要小，那麼依照排序邏輯，就將newV加入deque最後一個
   B. 若是newV比deque中最小的元素(last)要大，那麼代表在newV離開窗口前，last的元素都不可能是最大值(因為newV比last還要晚出現)，所以將last移出deque中
   C. 這個比較的過程不僅限1次，應該要重複比較到deque空了或著是newV小於last為止

這邊是利用deque拓展實作後的完整內容，其中的MyDeque就是依照上面思路實作拓展的內容

    class Solution {
        public int[] maxSlidingWindow(int[] nums, int k) {
            int[] result = new int[nums.length-k+1];
            int count = 0;
            MyDeque deque = new MyDeque();

            //先遍尋前k個值
            for(int i=0;i<k;i++) 
            {
                deque.Push(nums[i]);
            }

            //首次的result填入
            result[count] = deque.GetMax();
            count++;

            //開始滑動
            for(int i=k;i<nums.length;i++) 
            {               
                //先出後進
                deque.Poll(nums[i-k]);  
                deque.Push(nums[i]);
                result[count] = deque.GetMax();
                count++;
            }
            return result;
        }

        class MyDeque
        {
            Deque<Integer> que = new LinkedList<Integer>();         

            //滑動移出元素時 判斷移出的是否為最大的值，如果是的話就移除deque的first
            void Poll(int value) 
            {
                if(!que.isEmpty()&&value==que.peekFirst()) 
                {
                    que.pollFirst();
                }
            }

            //滑動新的元素進來 將所有小於value的元素排除後加入deque
            void Push(int value) 
            {
                while(!que.isEmpty()&&value>que.peekLast()) 
                {
                    que.pollLast();
                }
                que.addLast(value);
            }

            int GetMax() 
            {
                return que.peekFirst();
            }
        }
    }