Next Greater Element I
서로 다른 정수로 이루어진 두 배열 nums1과 nums2가 주어지며, nums1의 모든 값은 nums2에도 나타납니다. 값 x의 다음으로 큰 요소는 nums2에서 x의 오른쪽에 있는 값 중 x보다 큰 첫 번째 값이며, 그러한 값이 없으면 -1입니다.
nums1의 각 값에 대해 다음으로 큰 요소를 담은 배열을 nums1의 순서대로 반환하세요.
함수
- nums1integer-array
- 답해야 할 값들로, 모두 nums2에서 찾을 수 있습니다
- nums2integer-array
- 각 값의 오른쪽을 살펴보는 배열
- 반환값integer-array
- nums1의 각 값에 대해 다음으로 큰 요소를 nums1의 순서대로 표시하거나, 없으면 -1
제약 조건
1 ≤ nums1.length ≤ nums2.length ≤ 1040 ≤ nums1[i], nums2[i] ≤ 104-
nums1의 모든 값은 서로 다르고,nums2의 모든 값은 서로 다릅니다. -
nums1의 모든 값은nums2에 나타납니다.
예제
- 입력
- nums1 = [3, 8, 1]nums2 = [1, 6, 3, 8, 2]
- 출력
- [8, -1, 6]
- 설명
nums2에서 3 다음에는 8과 2가 오고, 8은 3보다 큰 첫 번째 값입니다. 8 다음에는 2만 있으므로 8에는 -1이 할당됩니다. 1 바로 뒤의 값은 6이며, 이미 더 큽니다.
- 입력
- nums1 = [5, 2]nums2 = [2, 9, 5, 4]
- 출력
- [-1, 9]
- 설명
- 5 뒤에는 4만 오고, 4가 더 작으므로 5는 -1을 받습니다. 2 바로 뒤의 값은 9입니다. 답은
nums2의 순서가 아니라nums1의 순서를 따릅니다.
- 입력
- nums1 = [10, 0]nums2 = [0, 10, 11]
- 출력
- [11, 10]
- 설명
- 10 다음의 첫 번째 값은 11입니다. 0 다음의 첫 번째 값은 10이며, 이 값이 더 크므로 11이 나중에 나오고 더 크더라도 0에는 10이 할당됩니다.
제출 시 숨은 테스트 +14개
후속 질문
nums2의 각 위치에 대해, 같은 한 번의 순회로 다음으로 큰 요소가 오른쪽으로 몇 단계 떨어져 있는지 반환할 수 있나요?
힌트
하나씩 열어 보세요. 열 때마다 조금 더 알려 줍니다.
nums1의 각 값 오른쪽을 탐색하면 값 하나당 최대 10^4단계가 걸릴 수 있습니다. 답은nums2에만 달려 있습니다. 한 번의 순회로nums2의 모든 값에 대한 다음으로 큰 원소를 구한 다음,nums1의 값들을 조회할 수 있을까요?nums2를 왼쪽에서 오른쪽으로 순회하면서 아직 더 큰 값을 만나지 못한 값들을 유지합니다. 새로운 값이 나오면, 그보다 작은 대기 중인 모든 값의 답이 됩니다. 대기 중인 값들은 항상 감소하는 수열을 이루므로, 더 작은 값들이 스택의 맨 위에 놓입니다.nums2의 각 값에 대해: 스택의 맨 위 값이 현재 값보다 작으면 맨 위 값을 꺼내고, 해시 맵에 현재 값을 그 값의 답으로 기록합니다. 그런 다음 현재 값을 넣습니다. 마지막에는 맵에서nums1의 각 값에 대한 답을 찾고, 한 번도 꺼내지지 않은 값에는 -1을 답으로 사용합니다.
풀이
값 하나에 대해서는 오른쪽을 탐색하면 되지만, nums1의 모든 값에 대해 탐색하면 최대 nums1.length × nums2.length단계가 걸립니다. 답은 nums2에만 달려 있으므로, 단조 스택으로 nums2의 모든 값에 대한 다음으로 큰 요소를 한 번에 찾고 해시 맵에 저장한 다음, 조회를 통해 nums1의 답을 구할 수 있습니다.
각 값을 찾아 오른쪽으로 살펴보세요
정답이지만 가장 큰 테스트에서는 끝나지 않음
핵심 아이디어
정의에 나온 대로 하면 됩니다. nums1의 값 x에 대해 nums2에서 x에 도달할 때까지 이동합니다. 그런 다음 계속 이동하다가 x보다 큰 첫 번째 값을 만나면 멈춥니다. 그런 값을 찾지 못한 채 끝에 도달하면 답은 -1입니다.
이 방법이 올바른 이유는 탐색이 x의 오른쪽에 있는 값들을 순서대로 방문하므로, 처음 만나는 더 큰 값이 그곳에 있는 첫 번째 더 큰 값이기 때문입니다.
답이 멀리 있거나 없는 경우에는 느립니다. nums2가 감소하는 배열이면 어떤 탐색도 더 큰 값을 찾지 못하고, nums1의 모든 값에 대해 끝까지 이동합니다. nums1에 값이 m개 있고 nums2에 값이 n개 있다면 최대 m × n번 이동하게 됩니다. 두 배열에 모두 10^4개의 값이 있으면 10^8번입니다. 각 탐색은 앞선 탐색이 이미 지나간 구간도 다시 지나갑니다.
알고리즘
nums1의 각 값x를 순회합니다.nums2[j]가x와 같은 인덱스j를 찾습니다.j+1부터nums2를 살펴보고x보다 큰 첫 번째 값에서 멈춥니다.- 그 값을 추가하거나, 탐색이 끝에 도달했다면 -1을 추가합니다.
- 모은 답을 반환합니다.
def nextGreaterElement(nums1, nums2):
result = []
for x in nums1:
j = 0
while nums2[j] != x:
j += 1
answer = -1
for k in range(j + 1, len(nums2)):
if nums2[k] > x:
answer = nums2[k]
break
result.append(answer)
return result단조 스택과 해시 맵
핵심 아이디어
질문을 거꾸로 생각해 보세요. 각 값에 대해 그다음에 무엇이 오는지 묻는 대신, nums2를 한 번 순회하면서 새로 등장하는 값이 자신보다 앞선, 더 작은 값들의 답이 되도록 하세요. 아직 답을 찾지 못한 값은 스택에 보관합니다. 값이 하나 등장하면 스택 맨 위에서 더 작은 값들을 모두 꺼냅니다. 새 값은 그 값들의 오른쪽에 있는 첫 번째 더 큰 값이므로, 바로 그 값들의 답입니다. 그런 다음 새 값을 스택에 넣습니다. 새 값도 자신의 답을 기다리고 있기 때문입니다.
nums2 = [1, 6, 3, 8, 2]를 따라가 보세요. 1을 넣습니다. 다음으로 6이 등장해 1보다 크므로, 1은 6에 대응됩니다. 그리고 6을 넣습니다. 다음으로 3이 등장하지만 6보다 크지 않으므로, 스택 맨 위에 넣습니다. 스택은 [6, 3]입니다. 다음으로 8이 3과 6을 꺼내므로, 둘 다 8에 대응됩니다. 그리고 8을 넣습니다. 마지막으로 2를 넣습니다. 스택은 [8, 2]로 끝나며, 이 두 값에는 답이 없습니다. nums1 = [3, 8, 1]의 경우 맵은 [8, -1, 6]을 반환합니다.
스택은 항상 아래에서 위로 갈수록 값이 작아집니다. 어떤 값을 넣기 전에 그 위에 있던 더 작은 값들을 모두 꺼내기 때문입니다. 따라서 맨 위만 확인하면 됩니다. 어떤 값은 처음으로 더 큰 값이 나타나는 순간 스택에서 빠지므로, 기록하는 답은 가장 큰 값이 아니라 처음 만나는 값입니다.
nums2의 각 값은 한 번씩 스택에 들어가고 최대 한 번 꺼내지므로, 전체 순회 동안 내부 루프에서 꺼내는 횟수는 모두 합쳐 최대 n회입니다. m번의 조회까지 포함하면 시간 복잡도는 O(n + m)입니다. 두 배열을 연결하는 것은 맵입니다. 값은 서로 다르므로, nums1과 nums2에서 위치가 다르더라도 값 자체를 안전한 키로 사용할 수 있습니다. C와 R 풀이에서는 값으로 인덱싱하는 10^4+1개 슬롯의 배열을 맵으로 사용합니다. 어떤 값도 10^4를 초과하지 않으므로 이 방법이 작동합니다.
알고리즘
- 빈 맵과 빈 스택을 만듭니다.
nums2의 각 값에 대해 스택 맨 위에서 더 작은 값을 모두 꺼내 현재 값에 매핑합니다.- 현재 값을 스택에 넣습니다.
nums1의 각 값에 대해 매핑된 답을 반환하거나, 매핑된 값이 없으면 -1을 반환합니다.
def nextGreaterElement(nums1, nums2):
next_greater = {}
stack = [] # values still waiting for a greater one, decreasing from bottom to top
for value in nums2:
# value is the first greater value to the right of every smaller value on the stack.
while stack and stack[-1] < value:
next_greater[stack.pop()] = value
stack.append(value)
# Whatever is still on the stack has no greater value to its right.
return [next_greater.get(x, -1) for x in nums1]
함정과 경계 사례
스택 자체는 짧은 코드입니다. 실수는 무엇을 기록하고 어디를 살펴보는지에서 발생합니다.
- 오른쪽에서 처음으로 더 큰 값이 아니라 가장 큰 값을 기록하는 경우입니다.
nums2 = [3, 5, 1, 2, 4, 9, 0]에서 1의 답은 9가 아니라 2입니다. nums2의 순서대로 답을 반환하거나,nums2의 모든 값에 대해 답을 반환하는 경우입니다. 결과에는nums1의 각 값에 대한 항목이 하나씩,nums1의 순서대로 들어갑니다.- 값 대신 인덱스를 반환하는 경우입니다. 문제에서 요구하는 것은 더 큰 값 자체입니다.
nums1에서 값이 있는 인덱스로nums2를 읽는 경우입니다. 같은 값도 두 배열에서 서로 다른 위치에 있으므로, 값으로 찾아야 합니다. 이것이 바로 맵을 사용하는 이유입니다.- 끝까지 스택에 남은 값들을 잊는 경우입니다. 이 값들은 더 큰 값을 만나지 않았으므로 답은 -1입니다. 기본값이 없는 맵 조회는 실패하거나 아무것도 반환하지 않습니다.
- 왼쪽을 살펴보거나
nums2의 시작 부분으로 되돌아가는 경우입니다. 오른쪽에 있는 값만 해당하며, 배열은 순환하지 않습니다.
자주 묻는 질문4
Next Greater Element I의 시간 복잡도는 얼마인가요?
단조 스택을 사용하는 해결 방법의 시간 복잡도는 O(n + m)이며, 여기서 n은 nums2의 길이이고 m은 nums1의 길이입니다. nums2의 각 값은 최대 한 번 푸시되고 한 번 팝되며, nums1의 각 값은 맵에서 한 번 조회됩니다. 맵과 스택은 O(n)의 공간을 사용합니다. 각 값에서 오른쪽으로 탐색하면 O(n·m)의 시간이 걸립니다.
단조 스택이란 무엇인가요?
바닥에서 위쪽으로 갈수록 값이 정렬된 상태를 유지하는 스택이며, 여기서는 내림차순입니다. 새 값을 푸시하기 전에 정렬 순서를 깨뜨리는 모든 값을 팝합니다. 실제 작업은 이 팝 과정에서 이루어집니다. 팝된 각 값은 오른쪽에서 자신보다 큰 첫 번째 값을 찾은 것입니다. 이 방법은 다음으로 큰 값, 다음으로 작은 값과 비슷한 문제를 선형 시간에 해결합니다.
Next Greater Element I에 해시 맵이 필요한 이유는 무엇인가요?
스택을 순회하면 값이 스택에서 빠져나오는 순서대로 답을 얻으며, 각 답은 nums2의 값에 대응합니다. 출력은 같은 값이 다른 위치에 있는 nums1의 순서를 따라야 합니다. 모든 값이 서로 다르므로, 값에서 답으로 매핑하는 맵을 사용하면 각 값을 상수 시간에 조회하여 두 배열을 연결할 수 있습니다.
nums2가 순환형이면 무엇이 달라지나요?
그런 다음 배열의 시작 부분부터 더 큰 값을 찾는 작업을 계속할 수 있습니다. i가 0부터 2n-1까지일 때 인덱스 i % n을 사용하여 배열을 두 번 순회하며, 첫 번째 순회에서만 값을 스택에 넣습니다. 두 번의 순회가 끝난 후에도 스택에 남아 있는 값은 어디에도 더 큰 값이 없으므로, 그 답은 -1입니다.
비슷한 문제
같은 아이디어를 쓰는 문제입니다. 두세 개를 풀면 패턴이 몸에 익습니다.
Python
def nextGreaterElement(nums1, nums2):
# 여기에 코드를 작성하세요케이스 1
케이스 2
케이스 3
입력
nums1 = [3, 8, 1] nums2 = [1, 6, 3, 8, 2]
기대값
[8, -1, 6]