Skip to content
Branch: master
Find file History
Fetching latest commit…
Cannot retrieve the latest commit at this time.
Permalink
Type Name Latest commit message Commit time
..
Failed to load latest commit information.
239. Sliding Window Maximum.go
239. Sliding Window Maximum_test.go
README.md

README.md

239. 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. Return the max sliding window.

Example:

Input: nums = [1,3,-1,-3,5,3,6,7], and k = 3
Output: [3,3,5,5,6,7] 
Explanation: 

Window position                Max
---------------               -----
[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

Note:

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

Follow up:

Could you solve it in linear time?

题目大意

给定一个数组 nums,有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口 k 内的数字。滑动窗口每次只向右移动一位。返回滑动窗口最大值。

解题思路

  • 给定一个数组和一个窗口为 K 的窗口,当窗口从数组的左边滑动到数组右边的时候,输出每次移动窗口以后,在窗口内的最大值。
  • 这道题最暴力的方法就是 2 层循环,时间复杂度 O(n * K)。
  • 另一种思路是用优先队列,每次窗口以后的时候都向优先队列里面新增一个节点,并删除一个节点。时间复杂度是 O(n * log n)
  • 最优的解法是用双端队列,队列的一边永远都存的是窗口的最大值,队列的另外一个边存的是比最大值小的值。队列中最大值左边的所有值都出队。在保证了双端队列的一边即是最大值以后,时间复杂度是 O(n),空间复杂度是 O(K)
You can’t perform that action at this time.