Candy -- LeetCode

原題鏈接: http://oj.leetcode.com/problems/candy/
這道題用到的思路和Trapping Rain Water是一樣的，用動態規劃。基本思路就是進行兩次掃描，一次從左往右，一次從右往左。第一次掃描的時候維護對於每一個小孩左邊所需要最少的糖果數量，存入數組對應元素中，第二次掃描的時候維護右邊所需的最少糖果數，並且比較將左邊和右邊大的糖果數量存入結果數組對應元素中。這樣兩遍掃描之後就可以得到每一個所需要的最最少糖果量，從而累加得出結果。方法只需要兩次掃描，所以時間復雜度是O(2*n)=O(n)。空間上需要一個長度為n的數組，復雜度是O(n)。代碼如下：

public int candy(int[] ratings) {
    if(ratings==null || ratings.length==0)
    {
        return 0;
    }
    int[] nums = new int[ratings.length];
    nums[0]=1;
    
    for(int i=1;iratings[i-1])
        {
            nums[i] = nums[i-1]+1;
        }
        else
        {
            nums[i] = 1;
        }
    }
    int res = nums[ratings.length-1];
    for(int i=ratings.length-2;i>=0;i--)
    {
        int cur = 1;
        if(ratings[i]>ratings[i+1])
        {
            cur = nums[i+1]+1;
        }
        res += Math.max(cur,nums[i]);
        nums[i] = cur;
    }
    return res;
}