📑 题目：121. 买卖股票的最佳时机

🚀 本题 LeetCode 传送门

题目大意

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。注意你不能在买入股票前卖出股票。

解题思路

• 题目要求找出股票中能赚的钱最多的差价
• 这一题也有多个解法，可以用 DP，也可以用单调栈

代码

package leetcode
// 解法一 模拟 DP
func maxProfit(prices []int) int {
 if len(prices) < 1 {
  return 0
 }
 min, maxProfit := prices[0], 0
 for i := 1; i < len(prices); i++ {
  if prices[i]-min > maxProfit {
   maxProfit = prices[i] - min
  }
  if prices[i] < min {
   min = prices[i]
  }
 }
 return maxProfit
}
// 解法二 单调栈
func maxProfit1(prices []int) int {
 if len(prices) == 0 {
  return 0
 }
 stack, res := []int{prices[0]}, 0
 for i := 1; i < len(prices); i++ {
  if prices[i] > stack[len(stack)-1] {
   stack = append(stack, prices[i])
  } else {
   index := len(stack) - 1
   for ; index >= 0; index-- {
    if stack[index] < prices[i] {
     break
    }
   }
   stack = stack[:index+1]
   stack = append(stack, prices[i])
  }
  res = max(res, stack[len(stack)-1]-stack[0])
 }
 return res
}