Leetcode: 캔디 개수가 인접수보다 커요.

원제 스탬프

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?

class Solution {
public:
    int candy(vector<int> &ratings) {
        std::vector<int> num(ratings.size(), 1);
        
        int inc = 2;
        for (int i = 1; i < ratings.size(); ++i) {
            if (ratings.at(i) > ratings.at(i - 1)) {
                num.at(i) = std::max(inc++, num.at(i));
            } else {
                inc = 2;
            }
        }
        inc = 2;
        for (int i = ratings.size() - 2; i >= 0; --i) {
            if (ratings.at(i) > ratings.at(i + 1)) {
                num.at(i) = std::max(inc++, num.at(i));
            } else {
                inc = 2;
            }
        }
        int res = std::accumulate(num.begin(), num.end(), 0);
        return res;
    }
};

step1. 우선 보조수 그룹의 모든 요소를 1로 초기화합니다. 왜냐하면 모든 요소가 적어도 1이기 때문입니다.
step2. 왼쪽에서 오른쪽으로 스캔합니다. 만약에 어떤 수가 왼쪽 인접수보다 크면num수조가 대응하는 위치의 이 수는 2부터 점차적으로 증가합니다. 그렇지 않으면 점차적으로 증가합니다.
반복이 끝난 후에 만족할 수 있다. 만약에 원수 그룹의 어떤 수가 왼쪽 인접수보다 크면 대응 보조수 그룹도 반드시 왼쪽 인접수보다 크다
만약에 ratings[i]>=ratings[i+1] 이때 ratings[i+1]는 반드시 1이다
step3. 오른쪽에서 왼쪽으로 훑어보기, step2 유사

사실 step2에서num.at(i)는 반드시 inc++와 같다. 왜냐하면num.at(i)가 바뀌기 전에는 모두 처음에 1이었기 때문이다.
왜 step3에 inc비num.at(i)의 비교를 꼭 넣어야 합니까?step2 이후 그룹의 크기 조건을 충족시켜야 하기 때문에

 ：1 --> 2 --> 5 --> 4 --> 3 --> 2 --> 1

step2  num ：1 --> 2 --> 3 --> 1 --> 1 --> 1 --> 1

step3 idx=2  : 1 --> 2 --> （3 or 5）--> 4 --> 3 --> 2 --> 1

idx=2 위치에서 왼쪽 인접수보다 크고 오른쪽 인접수보다 크다는 것을 만족시켜야 max 조작이 가능합니다

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

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

python 문자열 입력으로 모든 유효한 IP 주소 생성(LeetCode 93번 문제)

이 문제의 공식 난이도는 Medium으로 좋아요 1296, 반대 505, 통과율 35.4%를 눌렀다.각 항목의 지표로 말하자면 보기에는 약간 규범에 맞는 것 같지만, 실제로도 확실히 그렇다.이 문제의 해법과 의도는 ...

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

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

Leetcode: 캔디 개수가 인접수보다 커요.

좋은 웹페이지 즐겨찾기