Sharing my code... JAVA O(n) solution


  • 0
    D

    This is a O(n) time and O(1) space solution. treating the array as multiple hills,

    public class Solution {
        public int candy(int[] ratings) {
            if (ratings.length<2) return ratings.length;
            int sum = 0, index=0;
            while (index<ratings.length) {
                int cur = ratings[index], status = 0, up=1, down =1;
                while (index+1<ratings.length) {
                    int next = ratings[index+1];
                    if (status==0 && next==cur) {
                        sum++;
                    } else if (status<=1 && next>cur) {
                        status = 1;
                        up++;
                        cur = next;
                    } else if (next<cur) {
                        status = 2;
                        down++;
                        cur = next;
                    } else {
                        if (next>cur) {
                            index--;
                            sum--;
                        }
                        break;
                    }
                    index++;
                }
                sum += up * (up-1) /2;
                sum += down * (down-1) /2;
                sum += Math.max(up, down);
                index++;
            }
            return sum;
        }
    }
    

Log in to reply
 

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