//45.跳跃游戏
func canJump(nums []int) bool {
cover := 0
for i := 0; i <= cover; i++ {
cover = max(cover, i+nums[i])
if cover >= len(nums)-1 {
return true
}
}
return false
}
//45.跳跃游戏II
func jump(nums []int) int {
if len(nums)==1{
return 0
}
next, cur := 0, 0 //next记录下一个最大覆盖范围，cur记录当前覆盖范围
res := 0
for i := 0; i <= len(nums); i++ {
next = max(next, i+nums[i])
if i == cur {
if cur != len(nums)-1 {
cur = next
res++
if cur >= len(nums)-1 {
break
}
}
}
}
return res
}
//121.买卖股票的最佳时机
func maxProfit(prices []int) int {
low := math.MaxInt32 //int32最大值
result := 0
for i := 0; i < len(prices); i++ {
low = min(low, prices[i])
result = max(result, prices[i]-low)
}
return result
}
//763.划分字母区间
func partitionLabels(s string) []int {
m := make([]int,26)
left, right := 0, 0
res := []int{}
for i, _ := range s {
m[int(s[i]-'a')] = i //统计最远出现位置
}
for i, _ := range s {
right = max(right, m[int(s[i]-'a')])
if i == right {
res = append(res, right-left+1)
left = i + 1
}
}
return res
}
//56.合并区间
func merge(intervals [][]int) [][]int {
res := [][]int{}
sort.Slice(intervals, func(i, j int) bool {
return intervals[i][0] < intervals[j][0]
})
res = append(res, intervals[0])
for i := 1; i < len(intervals); i++ {
if res[len(res)-1][1] >= intervals[i][0] {
res[len(res)-1][1] = max(intervals[i][1], res[len(res)-1][1])
}else{
res=append(res,intervals[i])
}
}
return res
}