【LeetCode】135. 分发糖果

135. 分发糖果

参考图解

先按「左规则」得到下图：

再按「右规则」处理后如下图：

最终，取 max（左规则，右规则），才能同时满足左规则和右规则，得到结果如下图所示：

能做出来的难题

一、贪心

1.1 贪心

// go
func candy(ratings []int) int {
	LEN := len(ratings)
	// 初始化
	left := make([]int, LEN)
	right := make([]int, LEN)
	for i := 0; i < LEN; i++ {
		left[i] = 1
		right[i] = 1
	}
	// 应用左规则
	for i := 1; i < LEN; i++ {
		if ratings[i] &gt; ratings[i-1] {
			left[i] = left[i-1] + 1
		}
	}
	// 应用右规则
	for i := LEN - 2; i &gt;= 0; i-- {
		if ratings[i] &gt; ratings[i+1] {
			right[i] = right[i+1] + 1
		}
	}
	ans := 0
	for i := 0; i < LEN; i++ {
		v := max(left[i], right[i])
		ans += v
	}
	return ans
}

二、多语言解法

C

p

p

/

G

o

/

P

y

t

h

o

n

/

R

u

s

t

/

J

s

/

T

s

Cpp/Go/Python/Rust/Js/Ts

Cpp/Go/Python/Rust/Js/Ts

// cpp

// go 同上

# python

// rust

// js

// ts

代码007普通

打赏 收藏 海报 链接