Thursday, April 21, 2016

Window minimum

April 21, 2016

Try to get some algorithm reading and then find a similar algorithm in HackerRank, and get some workout on coding.

It is called Window minimum.

Problem statement from the geeksforgeeks website


Given an array of size N, a window of size W slides over it by increment of slide S. If the window reaches to the end, we should stop there. Find a formula in form of N, S, W so that we can find the number of valid windows. Write a program to find minimum in every window and print it. Optimize it.
e.g. {1,2,3,4,5}, W=2, S=1
first window: {1,2} min=1
second window(increment by S=1): {2,3}, min=2
last window: {4,5}, min=4
The array might not be sorted. I have taken sorted array for simplicity.

or in Chinese, 
滑动窗口求最小:
 给了一个ArrayList:4, 2, 12, 11, -5,窗口size为2,返回的ArrayList为:2, 2, 11, -5。这里窗口size是一个参数。

Leetcode 239: Sliding window maximum

Read one of solutions using Java:
Java solution 

No comments:

Post a Comment