LeetCode 239. Sliding Window Maximum
原題鏈接在這里:https://leetcode.com/problems/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?=?[1,3,-1,-3,5,3,6,7], and?k?= 3.
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:
題解:
用deque, 里面存index.
從尾部添加index前先檢查deque的尾部index對應的元素nums[deque.getLast()]是否比要添加的元素nums[i]小或者相等,若是,就把尾部index remove掉,一直remove直到遇到比nums[i]大的數或者LinkedList 為空。e.g. 當添加nums[1] = 3的index 1時,最大的數肯定是3,1就沒有用了。也就是說如果出現比先添加的數大的數時,先添加的就沒有用了。
如此deque里面保存的就是[第一大index, 第二大index, 第三大index, 第四大index...].
若是i - 頭部的index >= k, 就說明現在的window大小已經大于了k, 就需要從頭remove一次.
當 i+1>=k 是開始記錄res. res的坐標為i-k+1, 取ls的頭index, 也就是當前窗口的最大index. 把對應的元素加大res中。
Time Complexity: O(n). 每個元素最多進deque一次, 出deque一次. Space O(k).
AC Java:
1 public class Solution { 2 public int[] maxSlidingWindow(int[] nums, int k) { 3 if(k == 0){ 4 return new int[0]; 5 } 6 7 int [] res = new int[nums.length-k+1]; 8 LinkedList<Integer> deque = new LinkedList<Integer>(); 9 for(int i = 0; i<nums.length; i++){ 10 while(!deque.isEmpty() && nums[deque.getLast()]<=nums[i]){ 11 deque.removeLast(); 12 } 13 deque.addLast(i); 14 if(i - deque.getFirst() >= k){ 15 deque.removeFirst(); 16 } 17 if(i+1>=k){ 18 res[i+1-k] = nums[deque.getFirst()]; 19 } 20 } 21 return res; 22 } 23 }?
轉載于:https://www.cnblogs.com/Dylan-Java-NYC/p/4938106.html
總結
以上是生活随笔為你收集整理的LeetCode 239. Sliding Window Maximum的全部內容,希望文章能夠幫你解決所遇到的問題。
- 上一篇: 文化-梁晓声
- 下一篇: VIJOS【1234】口袋的天空