题目:122. 买卖股票的最佳时机 II
思路:
假如第 0 天买入,第 3 天卖出,那么利润为:prices[3] - prices[0]。
相当于(prices[3] - prices[2]) + (prices[2] - prices[1]) + (prices[1] - prices[0])。
此时就是把利润分解为每天为单位的维度,而不是从 0 天到第 3 天整体去考虑!
也就是说,只需要关注每天利润这个维度即可。
代码:
func maxProfit(prices []int) int {
res := 0
for i := 1; i < len(prices); i++ {
res += max(0, prices[i] - prices[i-1])
}
return res
}
func max(a,b int ) int {
if a > b {
return a
}
return b
}
参考:
题目:55. 跳跃游戏
思路:
其实就是不断更新最远能到达的位置,O(N)遍历一遍就可以了。超过能到达的最远位置就false,走到了最后就是true。
代码:
func canJump(nums []int) bool {
lens := len(nums)
mx := 0 // 最远到达位置
for i := 0 ; i < lens; i++ {
if i > mx { // 如果超出了最远到达位置就false
break
}
if i == lens - 1 { // 遍历到最后了 没问题
return true
}
mx = max(mx, i + nums[i]) // 更新最远位置
}
return false
}
func max(a,b int) int {
if a > b {
return a
}
return b
}
参考:
题目:45. 跳跃游戏 II
思路:
这个题比上一个要复杂一点,这个要记录更新区间的次数
代码:
func jump(nums []int) int {
lens := len(nums)
if lens == 1 {
return 0
}
res := 0
cur, next := 0, 0
for i:=0; i < lens; i++ {
next = max(nums[i]+i, next)
if next >= lens - 1 {
res ++
break
}
if i == cur {
cur = next
res++
}
}
return res
}
func max(a,b int) int {
if a > b {
return a
}
return b
}