> For the complete documentation index, see [llms.txt](https://syjohnson11.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://syjohnson11.gitbook.io/leetcode/14.greedy.md).

# 14.Greedy

## Candy

* 给定一堆小孩的评分
* 要求每个小孩至少有一颗糖果
* 如果小孩的评分比左右邻居的评分都高，就应该有更多的糖果
* using 1 array, 2 pass 
* first pass compare with left neighbor 
* second pass, compare with right neighbor

```
class Solution {
    /*
    using 1 array, 2 pass
    first pass, compare with left neighbor
    second pass, compare with right neighbor
    */
    public int candy(int[] ratings) {
        if (ratings == null || ratings.length == 0) return 0;
        int N = ratings.length;
        int[] candies = new int[N];
        Arrays.fill(candies, 1);
        //first pass, compare with left neighbor
        for (int i = 1; i < N; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        //second pass, compare with right neighbor
        for (int i = N - 2; i >= 0 ; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i+1] + 1, candies[i]); //要保证新的值不能比原来的值更小
            }
        }
        //collect sum
        int sum = 0;
        for (int candy : candies) {
            sum += candy;
        }
        return sum;
    }
}
```

## Partition Labels

* 给定string, 要求每个char最多只能在一个parition里出现
* 并且要求partition 越多越好
* try to find start and end index for each partition
* int last = S.lastIndexOf(S.charAt(start));&#x20;
* loop next pointer from start to last, find and update end idx&#x20;
* end = Math.max(end, S.lastIndexOf(S.charAt(next)));

```
public List<Integer> partitionLabels(String S) {
        List<Integer> res = new ArrayList<>();
        int len = S.length();
        int start = 0;
        while (start < len) {
            int last = S.lastIndexOf(S.charAt(start));
            int next = start + 1;
            int end = last;
            while (next < end) {
                end = Math.max(end, S.lastIndexOf(S.charAt(next)));
                next++;
            }
            res.add(end - start + 1);
            start = end + 1;
        }
        return res;
    }
```