题目大意：给你一个数组，让你输出移动窗口的最大值。
Problem:
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.
|
1 2 3 4 5 6 7 8 |
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 |
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?
Idea:
Solution 1: Brute Force
Time complexity: O((n – k + 1) * k)
Space complexity: O(1)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 |
// Author: Huahua // Running time: 180 ms class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ans; for (int i = k - 1; i < nums.size(); ++i) { ans.push_back(*max_element(nums.begin() + i - k + 1, nums.begin() + i + 1)); } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
// Author: Huahua // Running time: 80 ms class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (k == 0) return new int[0]; int[] ans = new int[nums.length - k + 1]; for (int i = k - 1; i < nums.length; ++i) { int maxNum = nums[i]; for (int j = 1; j < k; ++j) if (nums[i - j] > maxNum) maxNum = nums[i - j]; ans[i - k + 1] = maxNum; } return ans; } } |
Python
|
1 2 3 4 5 6 7 8 |
""" Author: Huahua Running time: 1044 ms """ class Solution: def maxSlidingWindow(self, nums, k): if not nums: return [] return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)] |
Solution 2: BST
Time complexity: O((n – k + 1) * logk)
Space complexity: O(k)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 82 ms class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { vector<int> ans; if (nums.empty()) return ans; multiset<int> window(nums.begin(), nums.begin() + k - 1); for (int i = k - 1; i < nums.size(); ++i) { window.insert(nums[i]); ans.push_back(*window.rbegin()); if (i - k + 1 >= 0) window.erase(window.equal_range(nums[i - k + 1]).first); } return ans; } }; |
Solution 3: Monotonic Queue
Time complexity: O(n)
Space complexity: O(k)
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 |
// Author: Huahua // Running time: 70 ms class MonotonicQueue { public: void push(int e) { while(!data_.empty() && e > data_.back()) data_.pop_back(); data_.push_back(e); } void pop() { data_.pop_front(); } int max() const { return data_.front(); } private: deque<int> data_; }; class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { MonotonicQueue q; vector<int> ans; for (int i = 0; i < nums.size(); ++i) { q.push(nums[i]); if (i - k + 1 >= 0) { ans.push_back(q.max()); if (nums[i - k + 1] == q.max()) q.pop(); } } return ans; } }; |
C++ V2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 |
// Author: Huahua // Running time: 65 ms class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> index; vector<int> ans; for (int i = 0; i < nums.size(); ++i) { while (!index.empty() && nums[i] >= nums[index.back()]) index.pop_back(); index.push_back(i); if (i - k + 1 >= 0) ans.push_back(nums[index.front()]); if (i - k + 1 >= index.front()) index.pop_front(); } return ans; } }; |
C++ V3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 |
// Author: Huahua // Running time: 67 ms class Solution { public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { deque<int> q; vector<int> ans; for (int i = 0; i < nums.size(); ++i) { while (!q.empty() && nums[i] > q.back()) q.pop_back(); q.push_back(nums[i]); const int s = i - k + 1; if (s < 0) continue; ans.push_back(q.front()); if (nums[s] == q.front()) q.pop_front(); } return ans; } }; |
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 |
// Author: Huahua // Running time: 19 ms class Solution { public int[] maxSlidingWindow(int[] nums, int k) { if (k == 0) return nums; int[] ans = new int[nums.length - k + 1]; Deque<Integer> indices = new LinkedList<>(); for (int i = 0; i < nums.length; ++i) { while (indices.size() > 0 && nums[i] >= nums[indices.getLast()]) indices.removeLast(); indices.addLast(i); if (i - k + 1 >= 0) ans[i - k + 1] = nums[indices.getFirst()]; if (i - k + 1 >= indices.getFirst()) indices.removeFirst(); } return ans; } } |
Python3
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
""" Author: Huahua Running time: 238 ms """ class MaxQueue: def __init__(self): self.q_ = collections.deque() def push(self, e): while self.q_ and e > self.q_[-1]: self.q_.pop() self.q_.append(e) def pop(self): self.q_.popleft() def max(self): return self.q_[0] class Solution: def maxSlidingWindow(self, nums, k): q = MaxQueue() ans = [] for i in range(len(nums)): q.push(nums[i]) if i >= k - 1: ans.append(q.max()) if nums[i - k + 1] == q.max(): q.pop() return ans |
Python3 V2
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 |
""" Author: Huahua Running time: 193 ms """ class Solution: def maxSlidingWindow(self, nums, k): indices = collections.deque() ans = [] for i in range(len(nums)): while indices and nums[i] >= nums[indices[-1]]: indices.pop() indices.append(i) if i >= k - 1: ans.append(nums[indices[0]]) if i - k + 1 == indices[0]: indices.popleft() return ans |