Python에서 오른쪽의 원형 큰 요소를 찾는 프로그램

nums라는 숫자 목록이 있다고 가정합니다. 인덱스 i의 값이 오른쪽에 있는 nums[i]보다 큰 다음 요소에 할당되는 동일한 길이의 새 목록을 찾아야 하며 필요할 때 목록의 맨 앞으로 다시 돌아갑니다. 더 큰 숫자가 없으면 -1로 설정해야 합니다.

따라서 입력이 [4, 5, 1, 3]과 같으면 출력은 [5, -1, 3, 4]

이 문제를 해결하기 위해 다음 단계를 따르겠습니다-

• n :=a

  의 크기

• stack :=스택, 처음에 0 삽입, res :=크기가 n인 목록 및 -1로 채우기

• 범위 0과 1의 각 값에 대해 수행

  • 0에서 n-1 사이의 i에 대해 수행

  • 스택이 비어 있지 않고 [스택 상단] 동안

    • res[스택 상단] :=a[i]

    • 스택에서 마지막 요소 삭제

  • 스택 끝에 i 삽입

• 반환 해상도

이해를 돕기 위해 다음 구현을 살펴보겠습니다. −

예

class Solution:
   def solve(self, a):
      n = len(a)
      stack, res = [0], [-1] * n
      for _ in range(2):
         for i in range(n):
            while stack and a[stack[-1]] < a[i]:
               res[stack[-1]] = a[i]
               stack.pop()
            stack.append(i)
   return res
ob = Solution()
nums = [4, 5, 1, 3]
print(ob.solve(nums))

입력

[4, 5, 1, 3]

출력

[5, -1, 3, 4]