A solution you can easily figure out during an interview - Topological Sort Solution
The actual rating of each child doesn\'t really matter. \nThe only thing matters is the relationship(larger/smaller) between two adjacent children, so we could 
The actual rating of each child doesn\'t really matter. \nThe only thing matters is the relationship(larger/smaller) between two adjacent children, so we could convert it to a graph problem.\nWe can do **topological sort** to this graph and give one more candy for each level of the graph.\n\nOne thing to note that we don\'t need to build this graph actually. Instead simply use an array to track indegree. \nThis could make the code concise and easier to implement during an interview.\n\n\n```\nclass Solution {\n    public int candy(int[] ratings) {\n        int n = ratings.length;\n        int[] ind = new int[n];\n        for(int i = 0; i < n; i++) {\n            if(i!=0 && ratings[i-1] > ratings[i]) ind[i-1]++;\n            if(i!=n-1 && ratings[i+1] > ratings[i]) ind[i+1]++;\n        }\n        Queue<Integer> q = new LinkedList<>();\n        for(int i = 0; i < n; i++)\n            if(ind[i] == 0) q.offer(i);\n        \n        int ans = 0;\n        int level = 1;\n        while(!q.isEmpty()) {\n            for(int k = q.size(); k > 0; k--) {\n                int idx = q.poll();\n                ans+=level;\n                if(idx!=0 && ratings[idx-1] > ratings[idx] && --ind[idx-1] == 0) q.offer(idx-1);\n                if(idx!=n-1 && ratings[idx+1] > ratings[idx] && --ind[idx+1] == 0) q.offer(idx+1);\n            }\n            level++;\n        }\n        return ans;\n    }\n}\n```
[]