Does anyone have a better idea?
My code is accepted with a run-time complexity of O(n) and a space complexity of nearly O(1), less than O(n).\n\nI deal with it for two times:\n\n1st, from left
My code is accepted with **a run-time complexity of O(n)** and **a space complexity of nearly O(1), less than O(n)**.\n\nI deal with it for two times:\n\n1st, from left to right, I add all the rising points, including the right edges without the left edges.\n\n2nd, from right to left, I add all the rising points, which are falling points at the 1st time, including the right and left edges.\n\nThere are 4 points should be noticed:\n\n1) The right edges must be dealt with for two times, so I only add the difference values or 0. I use a stack to mark every tops' candies except for the last child.\n\n2) The left edges are not dealt with for the 1st time, but they are dealt with for the 2nd time.\n\n3) For the flat parts, the left edges are dealt with as rising points, while the right edges are dealt with by adding 1 for the 1st time. So for the 2nd time, I add the values they should have then minus 1 when meeting the right edges. The rest are dealt with by adding 1 for the 1st time and not dealt with for the 2nd time.\n\n4) As to the point 0, I deal with it if it's less than or equal to point 1 by adding 1. If it's larger than point 1, I don't deal with it until the 2nd time is finished.\n\nHere is the code:\n\n    class Solution {\n    public:\n    \tint candy(vector<int> &ratings) {\n    \t\t// IMPORTANT: Please reset any member data you declared, as\n    \t\t// the same Solution instance will be reused for each test case.\n    \t\tif( ratings.size()<2 )\n    \t\t\treturn ratings.size();\n    \t\tint len=1, sum=0, flat=1, tmp;\n    \t\tvector<int> tops;\n    \t\tsum += ratings[0]>ratings[1] ? 0 : len ;\n    \t\tfor(int i=1; i<ratings.size(); ++i)\n    \t\t{\n    \t\t\tif( ratings[i]>ratings[i-1] )\n    \t\t\t\tsum += ++len;\n    \t\t\telse if( ratings[i]==ratings[i-1] )\n    \t\t\t{\n    \t\t\t\tlen = 1;\n    \t\t\t\tsum += 1;\n    \t\t\t}\n    \t\t\telse if( ratings[i]<ratings[i-1] && len!=1 )\n    \t\t\t{\n    \t\t\t\ttops.push_back(len);\n    \t\t\t\tlen=1;\n    \t\t\t}\n    \t\t}\n    \t\tlen=1;\n    \t\tfor(int i=ratings.size()-1; i>0; --i)\n    \t\t{\n    \t\t\tif( ratings[i]<ratings[i-1] )\n    \t\t\t\tsum += len++;\n    \t\t\tif( ratings[i]==ratings[i-1] )\n    \t\t\t{\n    \t\t\t\tsum += len-1;\n    \t\t\t\tlen = 1;\n    \t\t\t}\n    \t\t\telse if( ratings[i]>ratings[i-1] && len!=1 )\n    \t\t\t{\n    \t\t\t\ttmp = tops.back();\n    \t\t\t\ttops.pop_back();\n    \t\t\t\tsum += len>tmp?(len-tmp):0;\n    \t\t\t\tlen = 1;\n    \t\t\t}\n    \t\t}\n    \t\tsum += ratings[0]>ratings[1] ? len : 0 ;\n    \t\treturn sum;\n    \t}\n    };\n\nDoes anyone have a better idea? My code has a complicated judgement and seems not elegant enough.
[]