Min Max Riddle

Given an integer array of size , find the maximum of the minimum(s) of every window size in the array. The window size varies from  to .

For example, given , consider window sizes of  through . Windows of size  are . The maximum value of the minimum values of these windows is . Windows of size  are  and their minima are . The maximum of these values is . Continue this process through window size  to finally consider the entire array. All of the answers are .

Function Description

Complete the riddle function in the editor below. It must return an array of integers representing the maximum minimum value for each window size from  to .

riddle has the following parameter(s):

• arr: an array of integers

Input Format

The first line contains a single integer, , the size of . 
The second line contains  space-separated integers, each an .

Constraints

Output Format

Single line containing  space-separated integers denoting the output for each window size from  to .

Sample Input 0

4
2 6 1 12

Sample Output 0

12 2 1 1

Explanation 0

Here  and 

window size	window1	window2	window3	window4	maximum of all windows
1	2	6	1	12	12
2	2	1	1		2
3	1	1			1
4	1				1

Sample Input 1

7
1 2 3 5 1 13 3

Sample Output 1

13 3 2 1 1 1 1

Explanation 1

Here  and 

win size	w_1	w_2	w_3	w_4	w_5	w_6	w_7	maximum of all windows
1	1	2	3	5	1	13	3	13
2	1	2	3	1	1	3		3
3	1	2	1	1	1			2
4	1	1	1	1				1
5	1	1	1					1
6	1	1						1
7	1							1

Sample Input 2

6
3 5 4 7 6 2

Sample Output 2

7 6 4 4 3 2

Explanation 2

Here  and 

win size	w_1	w_2	w_3	w_4	w_5	w_6	maximum of all windows
1	3	5	4	7	6	2	7
2	3	4	4	6	2		6
3	3	4	4	2			4
4	3	4	2				4
5	3	2					3
6	2						2

---

이 문제는 각 원소의 n개 갯수만큼 묶었을 때 각각의 최소값을 구하고, 그 최소값 리스트에서의 최대값을 다시 구하는 문제이다.

의외로....쉽지 않았다....

일반적으로 각 원소의 n개 갯수만큼 묶었을 때 각각의 최소값을 구하는 것에서 문제가 끝나는데 거기서 다시 최대값을 구하라니...ㅠ

한 이틀을 고민한 끝에 문제를 풀긴 풀었는데............결국 테스트 케이스 3,4,5를 넘지 못하였다. 언제나 그렇듯 Timeout이 발생하였다.

왜 그런가 생각해보면, HackerRank에 있는 문제는 리스트를 돌면서 일일이 비교하는 것은 옳지 않다는 것을 계속 알려주고 있는것 같다.

무슨 얘기냐면, 원소의 갯수가 많아졌을 때 그 많은 원소를 일일이 비교하면서 최소값을 찾고, 다시 그 많은 원소들 중 최대값을 찾는 것은 비효율적이라고 보는 것이다.

그럼 어떻게 풀 수 있을까?

직접 코딩을 완성하지 못하였지만, 결국 일전에 풀었던 문제처럼 빠지는 원소와 들어가는 원소, 현재의 최소값을 비교하면서 값을 구해야 하는 것 같다.

즉, 

{ 1, 4, 3, 2, 5 } 라는 값이 주어졌을 때, 3번째 Win size를 구하는 경우 (1, 4, 3) 이 첫번째 목록인데, 두번째 목록에서 값을 구할 때 다시 (4, 3, 2)를 전체 비교하면서 구하는 것이 아니라, 빠지는 값 1, 들어오는 값 2, 현재 최소값 1 세 가지 값을 비교하면서 구해야 Timeout을 피할 수 있을 것이다.

일단 첫번째 코드만 남겨놓는다. ㅠ

*ps : 근데, 왜 이 문제가 Stack and Queue에 있을까? Stack이나 Queue를 이용하면 더 쉽게 풀 수 있는것일까??????