Stock Span Problem

Q: 주식 스팬 문제의 시간 복잡도는 얼마인가요?

단조 스택을 사용하면 각 날짜가 스택에서 최대 한 번만 빠져나오므로 시간 복잡도는 O(n) 이고 추가 공간은 O(n) 입니다. 가격이 계속 오르거나 그대로인 경우, 매일마다 거꾸로 순회하면 O(n²) 입니다.

Q: 스택에는 가격을 저장해야 할까요, 아니면 날짜 인덱스를 저장해야 할까요?

일 인덱스입니다. 범위는 일수이며, 이를 알려 주는 것은 차단자의 인덱스뿐입니다. prices[index] 는 비교를 위해 가격을 읽어옵니다.

Q: 주식 스팬 문제를 별도의 스택 없이 해결할 수 있을까요?

네. j = today - 1 에서 시작하세요. j ≥ 0 이고 prices[j] ≤ prices[today] 인 동안, 해당 구간에 속한 모든 날의 가격이 prices[j] 이하이므로 j - span[j] 로 건너뛰세요. 구간의 길이는 today - j 입니다. 건너뛴 위치는 스택에 들어갈 날에만 해당하므로, 이 순회는 O(n) 을 유지합니다.

Q: 주식 범위 문제는 이전의 더 큰 원소 문제인가요?

네, 일수로 측정합니다. 각 날짜에 대해 가격이 엄격히 더 높았던 가장 가까운 이전 날짜를 찾아 얼마나 이전인지 보고합니다. 탐색 방향이나 비교 조건을 바꾸면 같은 스택으로 다음으로 큰 값, 다음으로 작은 값 또는 이전의 더 작은 값을 구할 수 있습니다.

보통단조 스택

+10

매일 주식의 종가가 주어집니다. prices[i]는 i일의 가격입니다. i일의 범위는 i일을 끝으로 하고 해당 날짜를 포함하여, 가격이 prices[i] 이하인 날이 연속된 일수입니다.

prices와 같은 순서로 매일의 범위를 반환하세요. 각 범위는 최소 1입니다. 하루는 항상 자기 자신을 포함하기 때문입니다.

함수

stockSpan(prices: integer-array) → integer-array

pricesinteger-array: 각 날짜별 가격(순서대로)
반환값integer-array: 매일의 범위, 같은 순서로

제약 조건

1 ≤ prices.length ≤ 10⁴
1 ≤ prices[i] ≤ 10⁵
같은 가격인 이전 날짜도 기간에 포함되며, 가격이 엄격히 더 높을 때만 기간이 끝납니다.

예제

입력: prices = [31, 27, 14, 21, 30, 18, 40]
출력: [1, 1, 1, 2, 4, 1, 7]
설명: 3일째의 21은 14를 넘어 과거로 거슬러 올라가 27에서 멈춥니다: 범위 2. 4일째의 30은 31에서 멈춥니다: 범위 4. 6일째의 40은 이전의 모든 가격을 웃돌며 7일 전체를 포함합니다.

후속 질문

이제 가격이 한 번에 하나씩 들어오므로 가격이 들어올 때마다 각 구간을 보고해야 합니다. 어떤 접근 방식이 여전히 작동하며, 호출 사이에 무엇을 유지하나요?

풀이

하루의 범위는 가격이 엄격히 더 높은 가장 가까운 이전 날짜에서 끝납니다. 그 날짜를 찾으려면 거꾸로 살펴봐야 하며, 날짜마다 최대 n단계가 걸립니다. 대신 미래의 범위를 끝낼 수 있는 날짜만 유지하세요. 가격이 엄격히 내림차순인 인덱스 스택을 사용하면 한 번의 순회로 모든 경계를 찾을 수 있습니다.

매일 거꾸로 세기

정답이지만 가장 큰 테스트에서는 끝나지 않음

핵심 아이디어

정의를 따르세요. i일에는 그날의 가격이 prices[i] 이하인 동안 한 번에 하루씩 거슬러 올라가며, i일도 세세요. 처음으로 더 높은 가격이 나오거나 배열의 시작에 도달하면 탐색이 끝납니다.

이전 탐색 결과를 재사용하는 경우는 없습니다. 가격이 일정하거나 상승하는 경우 모든 탐색은 0일까지 거슬러 올라갑니다. n = 10^4일이면 약 5 × 10^7번의 단계가 필요합니다.

알고리즘

prices만큼 긴 배열 span을 만듭니다.
각 날짜 i마다 카운터를 0으로 설정하고 포인터 j를 i로 설정합니다.
j ≥ 0이고 prices[j] ≤ prices[i]인 동안 카운터에 1을 더하고 j를 하루 뒤로 이동합니다.
카운터를 span[i]에 저장합니다. 마지막 날짜가 지나면 span을 반환합니다.

def stockSpan(prices):
    span = []
    for i in range(len(prices)):
        count = 0
        j = i
        # Count today and every earlier day in a row that is not more expensive.
        while j >= 0 and prices[j] <= prices[i]:
            count += 1
            j -= 1
        span.append(count)
    return span

더 높은 날들의 단조 스택

핵심 아이디어

가격이 엄격히 더 높은 가장 가까운 이전 날짜를 차단 날짜라고 합니다. 구간은 today - blocker이며, 그런 날짜가 없으면 today + 1입니다.

첫 번째 예제에서 3일째의 가격은 21이고 4일째의 가격은 30입니다. 그 이후의 모든 순회는 먼저 4일째에 도달하며, 30을 넘어서는 가격은 모두 21도 넘으므로 3일째는 다시는 차단 날짜가 될 수 없습니다. 일반적으로 오늘이 되면 오늘 가격 이하인 이전 후보는 모두 역할을 마쳤으므로 꺼냅니다. 맨 위에 남은 날짜가 오늘의 차단 날짜입니다. 그런 다음 오늘을 넣습니다.

스택의 가격은 아래에서 위로 갈수록 엄격히 낮아지므로, 남아 있는 첫 번째 항목이 가장 가까운 더 높은 가격입니다. 첫 번째 예제에서 4일째는 3일째와 1일째를 꺼내고 0일째에서 멈추며, 구간은 4 - 0 = 4입니다. 각 날짜는 한 번씩만 들어가고 최대 한 번만 나오므로, 순회는 O(n)에 실행됩니다.

알고리즘

span 배열과 날짜 인덱스를 저장할 빈 스택을 만듭니다.
각 날짜 today에 대해, 스택에 있는 인덱스의 가격이 prices[today]보다 작거나 같은 동안 인덱스를 꺼냅니다.
스택이 비어 있으면 span은 today + 1이고, 그렇지 않으면 today에서 맨 위 인덱스를 뺀 값입니다.
today를 넣고 다음 날짜로 이동합니다. span을 반환합니다.

def stockSpan(prices):
    span = [0] * len(prices)
    higher = []  # indices of earlier days, prices strictly falling toward the top
    for today, price in enumerate(prices):
        # A day that is not more expensive than today can never stop a later span.
        while higher and prices[higher[-1]] <= price:
            higher.pop()
        # The span reaches back to the nearest more expensive day, or to day 0.
        span[today] = today - higher[-1] if higher else today + 1
        higher.append(today)
    return span

함정과 경계 사례

<= 대신 <에서 꺼내기. [8, 8, 3, 8]에서 마지막 날의 기간은 4입니다. 앞쪽의 8에서 멈추면 2가 됩니다.
스택이 비어 있을 때 today + 1 대신 today를 쓰기. 0일의 기간은 0이 아니라 1이어야 합니다.
하루에 한 번만 꺼내기. 첫 번째 예에서 40은 5일, 4일, 0일을 모두 처리해야 합니다. 5일에서 멈추면 4일이 차단 요소인 것처럼 보여 기간이 7이 아니라 2가 됩니다.
Lua와 R에서는 배열이 1부터 시작합니다. 인덱스가 1부터 시작하면 스택이 비어 있을 때의 기간은 today + 1이 아니라 today입니다.

자주 묻는 질문4

주식 스팬 문제의 시간 복잡도는 얼마인가요?

단조 스택을 사용하면 각 날짜가 스택에서 최대 한 번만 빠져나오므로 시간 복잡도는 O(n)이고 추가 공간은 O(n)입니다. 가격이 계속 오르거나 그대로인 경우, 매일마다 거꾸로 순회하면 O(n²)입니다.

스택에는 가격을 저장해야 할까요, 아니면 날짜 인덱스를 저장해야 할까요?

일 인덱스입니다. 범위는 일수이며, 이를 알려 주는 것은 차단자의 인덱스뿐입니다. prices[index]는 비교를 위해 가격을 읽어옵니다.

주식 스팬 문제를 별도의 스택 없이 해결할 수 있을까요?

네. j = today - 1에서 시작하세요. j ≥ 0이고 prices[j] ≤ prices[today]인 동안, 해당 구간에 속한 모든 날의 가격이 prices[j] 이하이므로 j - span[j]로 건너뛰세요. 구간의 길이는 today - j입니다. 건너뛴 위치는 스택에 들어갈 날에만 해당하므로, 이 순회는 O(n)을 유지합니다.

주식 범위 문제는 이전의 더 큰 원소 문제인가요?

네, 일수로 측정합니다. 각 날짜에 대해 가격이 엄격히 더 높았던 가장 가까운 이전 날짜를 찾아 얼마나 이전인지 보고합니다. 탐색 방향이나 비교 조건을 바꾸면 같은 스택으로 다음으로 큰 값, 다음으로 작은 값 또는 이전의 더 작은 값을 구할 수 있습니다.

def stockSpan(prices):
    # 여기에 코드를 작성하세요

테스트 #1

테스트 #2

테스트 #3

인자

prices = [31, 27, 14, 21, 30, 18, 40]

예상 출력

[1, 1, 1, 2, 4, 1, 7]