문제
You are given an integer array nums.
From any index i, you can jump to another index j under the following rules:
Jump to index j where j > i is allowed only if nums[j] < nums[i].
Jump to index j where j < i is allowed only if nums[j] > nums[i].
For each index i, find the maximum value in nums that can be reached by following any sequence of valid jumps starting at i.
Return an array ans where ans[i] is the maximum value reachable starting from index i.정수 배열 nums가 주어집니다.
인덱스 i에서 다른 인덱스로 이동할 수 있습니다. 이동 규칙은 다음과 같습니다.
현재 값보다 작은 값으로는 오른쪽으로만 이동할 수 있습니다.
현재 값보다 큰 값으로는 왼쪽으로만 이동할 수 있습니다.
즉, i에서 j로 이동하려면 다음 중 하나를 만족해야 합니다.
- j가 i보다 오른쪽에 있고 nums[j] < nums[i]
- j가 i보다 왼쪽에 있고 nums[j] > nums[i]
각 인덱스 i에 대해, i에서 시작해서 위 규칙대로 여러 번 이동했을 때 도달할 수 있는 값 중 최댓값을 구하세요.
각 위치 i의 답을 ans[i]에 담아 반환하세요.
예시
입력: nums = [2,1,3]
출력: [2,2,3]
설명:
- i = 0일 때: 더 큰 값으로 이동할 수 없습니다.
- i = 1일 때: nums[0] = 2가 nums[1] = 1보다 크므로, j = 0으로 이동할 수 있습니다.
- i = 2일 때: nums[2] = 3은 nums에서 가장 큰 값이므로, 더 큰 값으로 이동할 수 없습니다.
따라서 ans = [2, 2, 3]입니다.
제한
풀이
문제를 보면 알 수 있듯이, 숫자에서 숫자로 이동하는 것은 일단 양방향이다.
두 인덱스 i < j가 있다고 해보자.
만약 nums[i] > nums[j]라면,
i에서는 오른쪽에 있는 더 작은 값j로 이동할 수 있다.j에서는 왼쪽에 있는 더 큰 값i로 이동할 수 있다.
즉, 왼쪽 값이 오른쪽 값보다 큰 쌍이 하나라도 있으면, 그 두 위치는 서로 오갈 수 있다.
반대로 nums[i] <= nums[j]라면 이 두 위치 사이에서는 이동할 수 없다.
따라서 이 문제는 각 인덱스를 노드로 보고, 이동 가능한 위치끼리 연결된 구간을 찾는 문제로 볼 수 있다.
하지만 모든 쌍을 직접 비교하면 이라서 불가능하다.
구간을 나눌 수 있는 기준
어떤 위치 i를 기준으로 배열을 다음처럼 나눠보자.
left = nums[0:i+1]
right = nums[i+1:N]이때 왼쪽 구간과 오른쪽 구간 사이를 오갈 수 있으려면,
왼쪽에 있는 어떤 값이 오른쪽에 있는 어떤 값보다 커야 한다.
즉,
max(left) > min(right)이면 두 구간 사이에 이동 가능한 쌍이 존재한다.
반대로,
max(left) <= min(right)이면 왼쪽의 모든 값이 오른쪽의 모든 값보다 작거나 같다는 뜻이다.
이 경우에는 왼쪽에서 오른쪽으로도, 오른쪽에서 왼쪽으로도 이동할 수 없다.
따라서 이 지점에서 구간을 끊을 수 있다.
prefix maximum, suffix minimum
매번 max(left)와 min(right)를 구하면 느리므로 미리 배열을 만들어둔다.
maxima[i] = nums[0]부터 nums[i]까지의 최댓값
minima[i] = nums[i]부터 nums[N-1]까지의 최솟값예를 들어 nums = [2, 1, 3]이면,
maxima = [2, 2, 3]
minima = [1, 1, 3]이제 인덱스 i에서 구간을 끊을 수 있는지는 다음 조건으로 판단할 수 있다.
maxima[i] <= minima[i + 1]코드에서는 반대로,
if i != N - 1 and maxima[i] > minima[i + 1]:
continue라고 되어 있다.
즉, 아직 왼쪽 구간과 오른쪽 구간이 연결될 수 있으면 끊지 않고 넘어간다.
끊을 수 있는 지점이 나오면, 지금까지의 구간은 하나의 연결된 구간이다.
같은 구간 안의 답은 모두 같다
하나의 연결된 구간 안에서는 서로 이동할 수 있으므로, 그 구간에서 도달 가능한 최댓값은 구간의 최댓값이다.
그리고 구간의 끝이 i라면, 그 구간의 최댓값은 maxima[i]이다.
그래서 구간의 시작점부터 i까지 답을 한 번에 채운다.
while last <= i:
ans[last] = maxima[i]
last += 1여기서 last는 아직 답을 채우지 않은 구간의 시작 위치를 의미한다.
코드
class Solution:
def maxValue(self, nums: List[int]) -> List[int]:
N = len(nums)
maxima = [0] * N
minima = [0] * N
for i in range(N):
if i == 0:
maxima[i] = nums[i]
else:
maxima[i] = max(maxima[i - 1], nums[i])
for i in range(N - 1, -1, -1):
if i == N - 1:
minima[i] = nums[i]
else:
minima[i] = min(minima[i + 1], nums[i])
last = 0
ans = [0] * N
for i in range(N):
if i != N - 1 and maxima[i] > minima[i + 1]:
continue
while last <= i:
ans[last] = maxima[i]
last += 1
return ans예시로 보기
nums = [2, 1, 3]maxima와 minima는 다음과 같다.
maxima = [2, 2, 3]
minima = [1, 1, 3]인덱스 0에서 확인하면,
maxima[0] = 2
minima[1] = 12 > 1이므로 왼쪽 [2]와 오른쪽 [1, 3] 사이에 이동 가능한 쌍이 있다.
따라서 아직 구간을 끊지 않는다.
인덱스 1에서 확인하면,
maxima[1] = 2
minima[2] = 32 <= 3이므로 여기서는 구간을 끊을 수 있다.
즉, [2, 1]은 하나의 연결된 구간이고, 이 구간에서 도달 가능한 최댓값은 2다.
따라서 앞의 두 위치 답은 2가 된다.
마지막 3은 혼자 하나의 구간이므로 답은 3이다.
결과는 다음과 같다.
[2, 2, 3]복잡도
maxima를 한 번 만들고, minima를 한 번 만든다.
그리고 마지막으로 배열을 한 번 순회하면서 답을 채운다.
따라서 시간 복잡도는
이다.
추가로 사용하는 배열은 maxima, minima, ans이므로 공간 복잡도는
이다.
