AC JAVA solution O(n) time


  • 2
    W
    public class Solution {
        public int candy(int[] ratings) {
            int[] res = new int[ratings.length];
            for (int i = 1; i < ratings.length; i++) {
                if (ratings[i] > ratings[i - 1]) {
                    res[i] = res[i - 1] + 1;
                }
            }
            for (int i = ratings.length - 2; i >= 0; i--) {
                if (ratings[i] > ratings[i + 1] && res[i] <= res[i + 1]) {
                    res[i] = res[i + 1] + 1;
                }
            }
            int sum = 0;
            for (int i : res) sum += 1 + i;
            return sum;
        }
    }

Log in to reply
 

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