가장 큰 차이점을 찾으십시오. - O (n)

Question

저는 어려움을 겪고있는 코딩 문제에 대해 질문하고 있습니다.

정수의 배열이 주어지면, 가장 큰 값을 가진 값을 올바른 값으로 연결하여 배열을 반복합니다 (한 번만 허용됨). 가장 큰 차이점을 찾고 있습니다. 로 이동 [4] = 6

3,1에

[1,2,3,6,3,1,4,3,4,2,3] 

• 1,2,3- 이동 [7] = 4
• 3 [9] = 4
• 간다 2는 [11] = 3로 이동합니다.

이 문제의 가능한 해결책은 무엇입니까? 파이썬으로 해결할 수있는 해결책을 썼다. 이 경우 가장 큰 차이가 발견되었습니다 (1,2,3 go to [4]). 그런 다음 재귀 적으로 나머지 목록을 수행합니다. 목록의 한 번 반복으로 어떻게 달성 할 수 있습니까?

Answer 1

다음은 코드로 전환 할 수 있어야한다는 힌트입니다. 목록을 뒤로 이동하십시오.

다음과 같이 생각하십시오. 3은 4를 누르기 전까지 각 값의 오른쪽에 가장 큰 값입니다. 그런 다음 4는 다음 값을 누를 때까지 각 값의 오른쪽에있는 최대 값입니다. 샘플 출력에서와 같이 가장 큰 가장 큰 값을 찾으려면 다음 4를 누르십시오.) 등등.

O (N) 임시 공간을 사용할 수 있다면 가장 큰 값의 목록을 작성한 다음 역순으로 응답을 순서대로 인쇄 할 수 있습니다. (또는 재귀 적으로 스택에 O (N) 임시 공간을 넣을 수 있습니다.)