[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?
 
주의, 6554 같은 건 2121로 나눌 수 있어요. 숫자가 똑같아요. 사탕 수가 같을 필요는 없어요.
나의 사고방식은 각각 두 개의vector로 점차적으로 증가하고 감소하는 데 필요한 사탕을 저장하여 최종 결과는 두 개의 최대치를 얻는다
가중치 6 6 1 5 4 3 7 4 2 2 5 4 3 5
찾다 점증
찾기 체감 1 2 1 2 1 2 1 3 2 1 1 3 2 1 뒤 에서 앞 으로 찾다 처음 은 1 을 만나다 점차 증가 하는 것 에 그 앞 에서 찾 은 숫자 를 더하다
최종 1, 2, 1, 2, 1, 2, 1, 3, 2, 1, 1, 3, 2, 1, 2.

int candy(vector<int> &ratings) {

        int ans = 0;

        vector<int> candysUp(ratings.size(), 1);

        vector<int> candysDown(ratings.size(), 1);

        for(int i = 1; i < ratings.size(); i++) // 

        {

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

            {

                candysUp[i] += candysUp[i - 1];

            }

        }

        for(int i = ratings.size() - 2; i >= 0; i--) // 

        {

            if(ratings[i + 1] < ratings[i])

            {

                candysDown[i] += candysDown[i + 1];

            }

        }



        for(int i = 0; i < ratings.size(); i++)

        {

            ans += max(candysUp[i], candysDown[i]);

        }

        return ans;

    }

 
신은 한 번만 순환하는 사고방식:
사실 전체적인 사상은 위와 같지만 위에서 여러 번 순환해야 하는 것은 점증과 점감의 분리 처리 때문이다.체감할 때 가장 큰 숫자가 몇 개를 넣어야 할지 모르기 때문이다.
대신의 사고방식은 점차적으로 증가하는 것이다. 위와 같이 점차적으로 증가하지만 점차적으로 감소하는 것은 먼저 모두 1을 더하고 만약 뒤에 점차적으로 감소하면 이전에 적게 추가한 것을 다시 추가한다(예를 들어 앞에 nSeqLen 숫자가 1을 적게 추가하면 답을 직접 nSeqLen을 하나 더 추가한다).

    // 

    int candy2(vector<int> &ratings) {

    int nCandyCnt = 0;///Total candies

    int nSeqLen = 0;  /// Continuous ratings descending sequence length

    int nPreCanCnt = 1; /// Previous child's candy count

    int nMaxCntInSeq = nPreCanCnt;

    if(ratings.begin() != ratings.end())

    {

        nCandyCnt++;//Counting the first child's candy.

        for(vector<int>::iterator i = ratings.begin()+1; i!= ratings.end(); i++)

        {

            // if r[k]>r[k+1]>r[k+2]...>r[k+n],r[k+n]<=r[k+n+1],

            // r[i] needs n-(i-k)+(Pre's) candies(k<i<k+n)

            // But if possible, we can allocate one candy to the child,

            // and with the sequence extends, add the child's candy by one

            // until the child's candy reaches that of the prev's.

            // Then increase the pre's candy as well.



            // if r[k] < r[k+1], r[k+1] needs one more candy than r[k]

            if(*i < *(i-1))

            {

                //Now we are in a sequence

                nSeqLen++;

                if(nMaxCntInSeq == nSeqLen)

                {

                    //The first child in the sequence has the same candy as the prev

                    //The prev should be included in the sequence.

                    nSeqLen++;

                }

                nCandyCnt+= nSeqLen;

                nPreCanCnt = 1;

            }

            else

            {

                if(*i > *(i-1))

                { 

                    nPreCanCnt++;

                }

                else

                {

                    nPreCanCnt = 1;

                }

                nCandyCnt += nPreCanCnt;

                nSeqLen = 0;

                nMaxCntInSeq = nPreCanCnt;

            }   

        }

    }

    return nCandyCnt;

}