滑動窗口最大值

給定一個數(shù)組 nums，有一個大小為 k 的滑動窗口從數(shù)組的最左側(cè)移動到數(shù)組的最右側(cè)。你只可以看到在滑動窗口內(nèi)的 k 個數(shù)字。滑動窗口每次只向右移動一位。

返回滑動窗口中的最大值。

進(jìn)階：

你能在線性時間復(fù)雜度內(nèi)解決此題嗎？

示例:

輸入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
輸出: [3,3,5,5,6,7]
解釋:

滑動窗口的位置 最大值

---

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

提示：

1 <= nums.length <= 10^5
-10^4 <= nums[i] <= 10^4
1 <= k <= nums.length

解題思路

一： 移動窗口，掃描，獲取最大值，假設(shè)數(shù)組里有n個元素，算法的復(fù)雜度是O(n)。
二： 利用一個雙端隊列來保存當(dāng)前窗口中最大那個數(shù)在數(shù)組里的下標(biāo)，雙端隊列新的頭就是當(dāng)前窗口最大的那個數(shù)。通過該下標(biāo)，可以很快知道新窗口是否仍包含原來那個最大的數(shù)。如果不包含，我們就把舊數(shù)據(jù)同雙端隊列頭刪除。

java解法

 public int[] maxSlidingWindow(int[] nums, int k) {

        //處理邊界值, 定義變量消除魔法值

        int min = 2;

        if (nums==null||nums.length< min){

            return nums;

        }

        //創(chuàng)建雙向隊列

        Deque<Integer> deque = new LinkedList<>();

        //創(chuàng)建結(jié)果數(shù)組

        int[] result = new int[nums.length-k+1];

        for (int i = 0; i < nums.length; i++) {

            //判斷入值是否小于隊尾值，保證隊列大小順序，確保最大值位于對頭

            while (deque.size()!=0&&nums[deque.peekLast()]<nums[i]){

                deque.removeLast();

            }

            //將數(shù)據(jù)加入隊列

            deque.addLast(i);

            //移除超出窗口的數(shù)據(jù)

            if (deque.peekFirst()<=i-k){

                deque.removeFirst();

            }

            //從第k-1個值開始存入最大值

            if (i+1>=k){

                result[i+1-k] = nums[deque.peekFirst()];

            }

        }

        return result;

    }

總結(jié)

以上是生活随笔為你收集整理的LeetCoded第239题题解--滑动窗口最大值的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。