WA for last testcase.


  • 0
    V

    I pass 26/27 testcases, but for the last one, I output 20473 (expected 20474). Can you point out where I am wrong? My code is a O(n) time complex and O(1) space complex algorithm, with one scanning through.

    int candy(vector<int> &ratings) {
        int size = ratings.size();
        if(size < 2){
            return size;
        }
        int result = 0, up = 0, down = 0, last = 0;
        ratings.push_back(ratings[size - 1]);
        for(int i = 1; i < size + 1; i ++){
            if(ratings[i] > ratings[i - 1]){
                if(up > 0){
                    up ++;
                }else if (down > 0){
                    if(down > last){
                        result -= last;
                        result += down;
                    }
                    down --;
                    result += (down * (down + 1) / 2);
                    down = 0;
                    up = 1;
                }else{
                    up = 1;
                }
            }else if(ratings[i] < ratings[i - 1]){
                if(down > 0){
                    down ++;
                }else if(up > 0){
                    result += (up * (up + 1) / 2);
                    last = up;
                    up = 0;
                    down = 1;
                }else{
                    down = 1;
                }
            }else{
                if(up > 0){
                    result += (up * (up + 1) / 2);
                    last = 0;
                }
                if(down > 0){
                    if(down > last){
                        result -= last;
                        result += down;
                    }
                    down --;
                    result += (down * (down + 1) / 2);
                }
                up = 0;
                down = 0;
            }
        }
        ratings.pop_back();
        result += size;
        return result;
    }

  • 0
    S

    Could you please be so kind and explain the idea of the algorithm?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.