Find the largest number in sliding window

Asked Jul 03 '19 at 22:20

Active Jul 03 '19 at 22:20

Viewed 29 times

This is a algorithm question.

You have an array of intergers, and a window of size k, you want to find the maximum number within the window starting from each index. Then return an array.

Example:

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

The naive method takes O(nk) runtime, where n is the size of array.

Can anyone think of some algorithms that has a better run time?

asked Jul 03 '19 at 22:20

Yongcong Luo

Interesting question. Don't know if it's on topic, but interesting. – 500 - Internal Server Error Jul 03 '19 at 22:25
Found solution: https://leetcode.com/problems/sliding-window-maximum/solution/ – Yongcong Luo Jul 03 '19 at 22:38
You might want to post it as an answer here (or your own version, probably) - links rot. – 500 - Internal Server Error Jul 03 '19 at 22:41
This is a duplicate, and https://stackoverflow.com/a/17249084/585411 has a `O(n)` solution. – btilly Jul 03 '19 at 23:46

Find the largest number in sliding window

0 Answers0