Java | one-pass, O(1) space, 4-line solution
The general idea of one-pass solution with constant space is to use a few variables (rather than an array) to keep track of "how many candies are needed" in eac
The general idea of one-pass solution with constant space is to use a few variables (rather than an array) to keep track of "how many candies are needed" in each section (with the same trend of fluctuation) and to reset these variables at good timing (when the trend changes).\n\nThe main logic consist of only 4 lines of code, dealing with the increasing trend, the stable trend, the decreasing trend and the compensation settlement, respectively.\n\n**case 1: increasing trend**\nIf the current kid\'s rating is higher than its preceding term: we increment `inc` and add it to `sum`. A simple explanation is that if this kid\'s rating is higher than the preceding one, he/she should be assigned one more candy.\n\n**case 2: stable trend**\nIf the current kid\'s has the same rating with the preceding kid: we reset `inc` to be `0`.\n\n**case 3: decreasing trend**\nThis case is a bit of complicated.  We add `dec` to `sum`, then increment `dec`. After doing so, we check whether the decresing trend terminates or changes. If the current element is the last element, we say "the trend terminates". If the next kid\'s rating is not less than this one, we say "the trend changes". In either situation, a \'compensation settlement\' should be processed.\n\nThere are two tasks in the **compensation settlement**: first, we check whether `dec` is greater than `inc`, if so, we append their difference to `sum`. That is, `if (dec > ince) sum += (dec - inc); ` Note, `inc` is not updated in the decreasing section, it holds the peak value at the top of this downward slope. That\'s why we compare `inc` and `dec` and update `sum`. The second task is to reset `inc` and `dec` to `0`.\n\nThe following code combines these two tasks in one statement (which is not very readable yet makes the whole code block more \'compressed\').\n\n```\npublic int candy(int[] kid) {\n  int sum = kid.length;\n  int inc = 0;\n  int dec = 0;\n  \n  for (int i = 1; i < kid.length; ++i) {\n    if (kid[i - 1] < kid[i]) {\n\t  sum += (++inc);\n\t}\n\telse if (kid[i - 1] == kid[i]) {\n\t  inc = 0;\n\t}\n\telse {\n\t  sum += (dec++);\n      // compensation settlement\n\t  if (i + 1 == kid.length || kid[i] <= kid[i + 1])\n\t    sum += Math.max(dec - inc, dec = inc = 0);\n\t}\n  }\n  return sum;\n}\n```\n\n\n**Supplements:**\n1. `sum` is initialized with the value of `kid.length`, which means that we already give each kid at least one candy.\n\n2. why the default value of `inc` and `dec` are `0`\'s and why `sum` is updated in the form `(++inc)` and `(dec++)`? A simple explanation is that they (initial values and updating logic) are not fixed, however, they need to be consistent with each other (and other conditions). By comparing different initial values and corresponding update statements, I think the following code is concisest. You can, say, set the default value of `inc` to be `1` or set the default value of `dec` to be `-1`, etc. Yet, if so, you need also to adjust your code. \n\n\n\n\n\n\n\n\n\n
['Java']