Leetcode | Candy

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?
우선 제목에 대해higher rating get more candies, 하지만 equal이라면 이웃보다 많을 수도 있고, 이웃보다 적을 수도 있습니다.즉, rating=[2,4,4,4,4,4,2]를 가정하면 결과는 [1,2,1,2,1]가 될 수 있다.
연속 상승과 하락 추세에 대한 계수가 필요하다는 것을 분석해 보자.평행의 추세에 대해 중간은 모두 1로 설정할 수 있다.초기 상태는 평행 추세로 볼 수 있다.평행 추세가 상승(또는 하락) 추세에 이르렀을 때의 변화는 사실 처음과 같다.
평행 상태: 모든 어린이는 설탕 한 알만 줄 수 있다.예를 들어rating=[4,4,2], 그러면 결과는 [1,1,2]이다.
하강 상태: 하강 상태는 상승 추세의 초기 계수를 2로 설정해야 한다(하락은 실제적으로 1, 2,..., n으로 다시 뒤집어서 계수하고, 뒤집어서 마지막은 1이기 때문에 상승의 초기는 2). 그래야 하강에서 상승으로 정확하게 전환할 수 있다.예를 들어rating=[3,1,4], 계수는[1,2,2], 최종 결과는[2,1,2]이다.
상승 상태: 상승 상태는 하락 추세의 초기 계수를 1로 설정해야 한다.떨어지는 계수가 뒤집히는 것을 확보하기 위해 떨어지는 첫 번째 점은 상승하는 마지막 점의 설탕 수보다 적다.우리는 반드시 하락 추세를 계산할 때, 만약 이전 상승 추세의 최대 추세보다 크거나 같으면, 우리는 최종 계수에 1을 더해야 한다.예를 들어 rating=[1,3,6,5,4,3,2,1], 계수는[1,2,3,2,3,4,5,3,2,1]이고 하락세 부분은 뒤집으면 [1,2,3,5,4,3,2,1]이다. 하락계수>=3일 때 1을 누적할 수 있다. 이 부분1은 상승세의 마지막 수인 [1,2,6,5,4,3,2,1]로 볼 수 있다.
초기 상태: N>1에 대해 첫 번째는 직접 계산할 수 있고 2부터 i원소와 i-1원소를 비교하여 어느 상태에 있는지 판단할 수 있다.초기 상태는 평행 상태와 같습니다.위의 분석에 의하면 상승 추세의 초기치는 2이고 하락 추세의 초기치는 1이다.이전 상승 추세의 최대치는 1이다. 

 1 class Solution {

 2 public:

 3     int candy(vector<int> &ratings) {

 4         int n = ratings.size();

 5         if (n <= 1) {

 6             return n;

 7         }

 8         

 9         int sum = 1, increasing = 2, decreasing = 1, maxIncreasing = 1;

10         

11         for (int i = 1; i < n; ++i) {

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

13                 maxIncreasing = increasing;

14                 sum += increasing++;

15                 decreasing = 1;

16             } else if (ratings[i] == ratings[i - 1]) {

17                 increasing = 2;

18                 decreasing = 1;

19                 maxIncreasing = 1;

20                 sum++;

21             } else {

22                 sum += decreasing++;

23                 if (decreasing > maxIncreasing) {

24                     sum++;

25                 }

26                 increasing = 2;

27             }

28         }

29         

30         return sum;

31     }

32 };

시간 복잡도 O(n), 공간 복잡도 O(1).
두 번째 브러시, 생각대로 쓰세요. 16줄에 걸렸어요.상승세라면 pre를 갱신해야 한다.pre는 상승세의 최대치다.pre의 초기값은 매우 클 것이다.120ms

 1 class Solution {

 2 public:

 3     int candy(vector<int> &ratings) {

 4         int n = ratings.size();

 5         if (n <= 1) return n;

 6         

 7         int sum = 1, pre = ratings.size() + 1, candy = 1, state = -1;

 8         

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

10             if (ratings[i - 1] < ratings[i]) {

11                 if (state == -1 || state == 1) {

12                     candy++;

13                 } else {

14                     candy = 2;

15                 }

16                 pre = candy;

17                 state = 1;

18             } else if (ratings[i - 1] > ratings[i]) {

19                 if (state == -1 || state == 0) {

20                     candy++;

21                     if (candy >= pre) sum++;

22                 } else {

23                     candy = 1;

24                 }

25                 state = 0;

26             } else {

27                 candy = 1;

28                 state = -1;

29                 pre = ratings.size() + 1;

30             }

31             sum += candy;

32         }

33 

34         return sum;

35     }

36 };

 Method II

인터넷에는 또 다른 해결 방향이 있는데 두 번 쓸어야 한다. 한 번은 왼쪽에서 오른쪽으로, 한 번은 오른쪽에서 왼쪽으로 쓸어야 한다. 이렇게 해서 두 개의 최소 당수 그룹을 얻고 마지막으로 이 두 데이터의 각 위치에 대해 최대치를 구하면 된다.이러한 시간 복잡도는 여전히 O(n)이고 공간 복잡도 역시 O(n)이다.사상은 Trapping Rain Water와 유사하다.
z신과 토론을 했는데 z신은 O(n) 공간이 필요 없는 방법을 제시했는데 생각해 봐도 그렇다.
두 개의 바늘이 있는데 왼쪽 바늘은 현재 위치의 왼쪽이 연속적으로 줄어드는 경계 위치를 가리킨다.오른쪽 바늘은 현재 위치의 오른쪽이 연속적으로 줄어드는 경계 위치를 가리킨다.
각 위치의 설탕 수는 max(cur-left,right-cur)+1에 의해 결정된다.
하지만 같은 상황에 추가로 주의해야 한다.만약ratings[i]==ratings[i-1]라면left=cur;만약ratings[i]==ratings[i+1]라면right=cur;
왼쪽 바늘의 업데이트는 O(n)에서 할 수 있으며, 오른쪽 바늘의 업데이트는 O(2n)가 가장 마음에 든다.
오른쪽의 체감 서열에 대해 오른쪽 바늘의 업데이트는right<=cur일 때만 업데이트할 필요가 있습니다.만약right>cur, 현재 체감 서열에 있음을 증명하기 때문에right는 변하지 않습니다.(Line14)

 1 class Solution {

 2 public:

 3     int candy(vector<int> &ratings) {

 4         int n = ratings.size();

 5         if (n <= 1) return n;

 6         ratings.push_back(ratings.back() + 1);

 7         int sum = 0, l = 0, r = 0, candy1 = 0;

 8         for (int i = 0; i < n; ++i) {

 9             if (i == 0 || ratings[i] <= ratings[i - 1]) {

10                 l = i;

11             } 

12             if (ratings[i] <= ratings[i + 1]) {

13                 r = i;

14             } else if (r <= i) {

15                 r = i;

16                 for (int j = i + 1; ratings[j] < ratings[j - 1]; ++j) r++;

17             }

18             sum += max(r - i, i - l) + 1;

19         }

20         ratings.pop_back();

21         return sum;

22     }

23 };

 136ms
라인 14가 없으면 1780ms입니다.
세 번째 브러시, 가장 쉽게 생각나는 것은 정반대 방향으로 한 번 쓸어내리는 방법이다.한 번쯤은 해봤겠지.i는 항상++i로 쓰기 쉽다.

 1 class Solution {

 2 public:

 3     int candy(vector<int> &ratings) {

 4         if (ratings.empty()) return 0;

 5         int n = ratings.size();

 6         vector<int> dp(n, 0);

 7         for (int i = 1; i < n; ++i) {

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

 9                 dp[i] = dp[i - 1] + 1;

10             }

11         }

12         

13         int min = 0, right = 0;

14         for (int i = n - 1; i >= 0; --i) {

15             if (i != n - 1 && ratings[i] > ratings[i + 1]) {

16                 right++;

17             } else {

18                 right = 0;

19             }

20             min += max(dp[i], right) + 1;

21         }

22         return min;

23     }

24 };