배열 nums와 다른 값 k가 있다고 가정하면 크기 k의 nums에서 가장 경쟁력 있는 부분 시퀀스를 찾아야 합니다. 여기서 하위 시퀀스 s1은 s1과 s2가 다른 첫 번째 위치에서 하위 시퀀스 s1이 s2의 해당 숫자보다 작은 숫자를 갖는 경우 하위 시퀀스 s2(동일한 크기)보다 경쟁력이 있습니다.
따라서 입력이 nums =[4,6,3,7] k =2와 같으면 크기가 2인 모든 부분 시퀀스 중에서 {[4,6], [4, 3], [4,7], [6,3], [6,7], [3,7]}, [3,7]이 가장 경쟁력이 있습니다.
이 문제를 해결하기 위해 다음 단계를 따릅니다. −
- 시도 횟수:=숫자 크기 - k
- 스택 :=새 목록
- 숫자 단위의 각 숫자에 대해 다음을 수행합니다.
- 스택이 비어 있지 않고 num <스택의 상단 및 시도> 0인 동안 do
- 스택에서 요소 팝
- 시도 횟수:=시도 횟수 - 1
- num을 스택에 푸시
- 스택이 비어 있지 않고 num <스택의 상단 및 시도> 0인 동안 do
- 스택의 상위 k개 요소 반환
예시
이해를 돕기 위해 다음 구현을 살펴보겠습니다. −
def solve(nums, k):
attempts = len(nums) - k
stack = []
for num in nums:
while stack and num < stack[-1] and attempts > 0:
stack.pop()
attempts -= 1
stack.append(num)
return stack[:k]
nums = [4,6,3,7]
k = 2
print(solve(nums, k)) 입력
[4,6,3,7], 2
출력
[3,7]