题解 | #分糖果问题#

独立写出来，思路有点借鉴单调栈的思路

class Solution {
public:
    /**
     * pick candy
     * @param arr int整型vector the array
     * @return int整型
     */
    int candy(vector<int>& arr) {
      int res = 0;
      //  dp[i] 代表第i个孩子分的的糖果数
      std::vector<int> dp(arr.size(), 1);
      
      //  需要和两边的人比，这里如果比两边的都高，那么需要比旁边最高的人多1
      //  使用两次比较，一次从左到右，一次从右到左，确保每个人对应的糖果能够比旁边分低的高
      for (int i = 1; i < arr.size(); ++i) {
        if (arr[i] > arr[i - 1]) {
          dp[i] = dp[i - 1] + 1;
        }
      }
      
      for (int i = arr.size() - 2; i >= 0; --i) {
        if (arr[i] > arr[i + 1]) {
          dp[i] = std::max(dp[i], dp[i + 1] + 1);
        }
      }
      
      for (int i = 0; i < arr.size(); ++i) {
        res += dp[i];
      }
      
      return res;
    }
};