By

当求一个数列的尖峰值，或者跟尖峰值相关的问题时，常常需要用到双向扫描的做法。

例如 LeetCode 105 Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:
(1) Each child must have at least one candy.
(2) Children with a higher rating get more candies than their neighbors.
What is the minimum candies you must give?

解法： 首先正向扫描，算出需要满足只看左边所需要的最少糖果的分配方案。
再反向扫描，算出满足只看右边所需要的最少糖果的分配方案。
然后分别对每一项求出两者之间的较大值。
可以优化为：反向扫描的时候，如果不满足高分小孩拿到比右边小孩更多糖果这个条件，再对值进行修正。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
var candy = function(ratings) {
	if (!ratings || ratings.length === 0)
	{
		return 0;
	}
	
	var number = [1];
	for (var i=1; i<ratings.length; i++)
	{
		if (ratings[i] > ratings[i-1])
		{
			number[i] = number[i-1] + 1;
		}
		else
		{
			number[i] = 1;
		}
	}
	
	for (var i=ratings.length-2; i>=0; i--)
	{
		if (ratings[i] > ratings[i+1] && number[i] <= number[i+1])
		{
			number[i] = number[i+1] + 1;
		}
	}
	
	var sum = 0;
	for (var i=0; i<ratings.length; i++)
	{
		sum += number[i];
	}
	
	return sum;
};