用l,r区间维护当前能跳跃的区间,计算当前区间能跳跃到的最右区间,以此更新r
当r >= len(nums) - 1就可以返回了
func jump(nums []int) int {
l, r := 0, 0
cnt := 0
for r < len(nums) - 1 {
max_r := r
for l <= r {
max_r = max(max_r, nums[l] + l)
l++
}
r = max_r
cnt++
}
return cnt
}
本质是合并区间,记录每个字符最后一次出现位置last
从左往右遍历s,根据last[i]
试图扩大l,r区间(初始为0,0),若r == i
说明无法扩大区间,维护ans
func partitionLabels(s string) []int {
last := [26]int{}
ans := []int{}
for i, c := range s {
last[c - 'a'] = i
}
l, r := 0, 0
for i, c := range s {
r = max(r, last[c - 'a'])
if r == i {
ans = append(ans, r - l + 1)
l = r + 1
}
}
return ans
}