算法
单调队列
时间复杂度: O(n)
空间复杂度: O(n)
C++代码
class Solution {
public:
static vector<int> maxSlidingWindow(const vector<int> &nums, const int k) {
const int n = static_cast<int>(nums.size());
vector<int> res;
if (n < k || k <= 0) {
return res;
}
deque<int> deque0;
for (int i = 0; i < n; ++i) {
if (!deque0.empty() && deque0.front() + k <= i) {
deque0.pop_front();
}
while (!deque0.empty() && nums[deque0.back()] <= nums[i]) {
deque0.pop_back();
}
deque0.push_back(i);
if (i + 1 >= k) {
res.push_back(nums[deque0.front()]);
}
}
return res;
}
};
Java代码
未完待续
Python3代码
from collections import deque
class Solution:
def maxSlidingWindow(self, nums: list, k: int) -> list:
res = []
n = len(nums)
if n < k or k <= 0:
return res
deque0 = deque()
for i in range(n):
if deque0 and deque0[0] + k <= i:
deque0.popleft()
while deque0 and nums[deque0[-1]] <= nums[i]:
deque0.pop()
deque0.append(i)
if i + 1 >= k:
res.append(nums[deque0[0]])
return res
Go代码
func maxSlidingWindow(nums []int, k int) []int {
n := len(nums)
if n < k || k <= 0 {
return []int{}
}
res := make([]int, n-k+1)[:0]
deque0 := make([]int, n)[:0]
for i := 0; i < n; i++ {
if len(deque0) > 0 && deque0[0]+k <= i {
deque0 = deque0[1:]
}
for len(deque0) > 0 && nums[deque0[len(deque0)-1]] <= nums[i] {
deque0 = deque0[:len(deque0)-1]
}
deque0 = append(deque0, i)
if i+1 >= k {
res = append(res, nums[deque0[0]])
}
}
return res
}