algorithm - 找到滑动窗口中的最大数

Question

这是一道算法题。

你有一个整数数组和一个大小为 k 的窗口，你想从每个索引开始找到窗口内的最大数字。然后返回一个数组。

例子：

input: [1,3,2,4,3,5,6,3,8]
window size = 3;
output:[3,4,4,5,6,6,6,8,8]

朴素的方法需要 O(nk) 运行时间，其中 n 是数组的大小。

谁能想到一些运行时间更好的算法？

标签： algorithmsliding-window