제목

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

Each child must have at least one candy.

Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

인터페이스

int candy(int[] ratings)

몇 명의 아이들이 일렬로 서 있는데 각 아이는 등급이 있다. 현재 아이에게 사탕을 주고 보낼 때 두 가지 규칙을 준수해야 한다. (1) 아이마다 적어도 사탕 한 알(2) 두 개의 인접한 아이 중에서 등급이 큰 아이는 등급이 작은 아이보다 사탕이 많으므로 사탕 수의 최소치를 구한다.

2 사고방식

기본 사고방식: 먼저 두 번의 스캐닝을 하고 한 번은 왼쪽에서 오른쪽으로, 한 번은 오른쪽에서 왼쪽으로 한다.마지막 스캐닝은 결과를 누적해 냈다.
첫 번째 스캐닝: 모든 아이의 왼쪽에 필요한 최소한의 사탕 수량을 유지하고 수조에 해당하는 원소에 저장합니다.
두 번째 스캐닝: 오른쪽 유지에 필요한 최소 사탕 수.
세 번째 스캐닝: 왼쪽과 오른쪽의 큰 사탕 수량을result에 누적하여 결과를 얻는다.
example: ratings = [3,4,5,1,2,3]

ratings
삼
사
오
일
이
삼
lefts
일
이
삼
일
이
삼
rights
일
일
이
일
일
일
양자 최대치
일
이
삼
일
이
삼
result = sum(1,2,3,1,2,3) = 12

복잡도

방법은 세 번만 스캔해야 하기 때문에 시간 복잡도는 O(3*n)=O(n)이다.공간에는 길이가 n인 두 개의 그룹이 필요하며 복잡도는 O(n)이다.

3 코드

 1     public int candy(int[] ratings) {

 2         final int len = ratings.length;

 3         int[] lefts = new int[len];

 4         int[] rights = new int[len];

 5 

 6         // scan from left to right

 7         lefts[0] = 1;

 8         for (int i = 1; i < len; i++) {

 9             if (ratings[i] > ratings[i - 1]) {

10                 lefts[i] = lefts[i - 1] + 1;

11             } else {

12                 lefts[i] = 1;

13             }

14         }

15 

16         // scan from right to left

17         rights[len - 1] = 1;

18         for (int i = len - 2; i >= 0; i--) {

19             if (ratings[i] > ratings[i + 1]) {

20                 rights[i] = rights[i + 1] + 1;

21             } else {

22                 rights[i] = 1;

23             }

24         }

25 

26         // calculate min nums of candy 

27         int result = 0;

28         for (int i = 0; i < len; i++) {

29             result += Math.max(lefts[i], rights[i]);

30         }

31         return result;

32     }

4 총결산

어린이가 설탕을 나누는 데 영향을 주는 요소는 모두 좌우 양쪽의 최치에 의해 결정된다.

이런 양쪽 스캐닝 방법은 비교적 자주 사용하는 기교이다. LeetCodeTrapping Rain Water와 이 문제를 모두 사용했다. 이런 방법을 자신의 사고방식의 일부로 삼을 수 있다. 보통 요구하는 변수와 좌우 원소가 관계가 있는 문제를 사용한다.From Code Ganker

code는 세 번째 스캐닝을 줄이고 세 번째 스캐닝을 두 번째 스캐닝에 넣을 수 있습니다. 지금은 추천하지 않습니다. 왜냐하면 문제 해결 방향이 뚜렷하지 않기 때문입니다.

5 확장

Trapping Rain Water

6 참조

leetcode
코드 Ganker 정복 코드
JustDoIT
밥 잘 하는 영자

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

면접 예상 질문: CSS, Javascript 고급

position 속성이란? display 속성이란? flex: 1차원 (가로 or 세로) 적으로 배치할 수 있는 방식 grid: 2차원 (가로, 세로 동시에) 적으로 배치할 수 있는 방식 reset.css vs. s...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

lc 면접 준비: 캔디

제목