문제
Take every contiguous window of span digits and multiply its digits. Return the largest product. Leading zeros are ordinary digits; a window containing zero has product zero. Do not reorder or skip digits.
Implement largest_adjacent_digit_product(digits, span).
Input
digits: The digit sequence, including any leading zeros.
span: The exact number of adjacent digits in a window.
Output
Return the greatest product over all windows of this width.
제약 조건
1 ≤ digit-string length ≤ 100,000. Characters are 0…9. 1 ≤ span ≤ min(18, length). All products fit signed 64-bit.
예시
입력:
span = 2
digits = "23405"
예상 출력:
expected = 12입력:
long long span = 2;
std::string digits = "23405";
예상 출력:
long long expected = 12;입력:
long span = 2;
string digits = "23405";
예상 출력:
long expected = 12;설명
The windows 23, 34, 40, and 05 have products 6, 12, 0, and 0. The largest is 12.
입력:
span = 3
digits = "102"
예상 출력:
expected = 0입력:
long long span = 3;
std::string digits = "102";
예상 출력:
long long expected = 0;입력:
long span = 3;
string digits = "102";
예상 출력:
long expected = 0;설명
There is only one width-three window. It contains zero, so 1 × 0 × 2 = 0.
접근 방법
먼저 스스로 풀어 본 뒤 힌트를 하나씩 열어 보세요.
힌트 1
윈도 안에 0이 있으면 곱은 0이 되므로, 연속된 비0 구간만 최대값에 기여할 수 있습니다.
힌트 2
슬라이딩 윈도나 숫자 구간별 곱을 추적해 매 구간을 처음부터 다시 계산하지 마세요.
힌트 3
정확한 길이를 주의하세요: 앞의 0도 자릿수로 세고, span이 비0 구간보다 길면 곱은 0입니다.
예상 복잡도
시간 O(n), 추가 공간 O(1)
참고 자료
이 문제는 CodeUtility에 맞게 수정되었습니다. 위의 설명과 제한 조건을 따르세요.