目录
121-买卖股票的最佳时机I
访问量:1323

一、题目

题目地址:https://leetcode.com/problems/best-time-to-buy-and-sell-stock

给定一个数组,它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易(即买入和卖出一支股票),设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。


示例 1:

输入: [7,1,5,3,6,4]

输出: 5

解释: 在第 2 天(股票价格 = 1)的时候买入,在第 5 天(股票价格 = 6)的时候卖出,最大利润 = 6-1 = 5 。注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。


示例 2:

输入: [7,6,4,3,1]

输出: 0

解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

二、求解

1、穷举法

func maxProfit(prices []int) int {
   var len int = len(prices)
   var i int
   var j int
   var rsMaxPro int = 0 //最终的最大值
   var curMaxPro int = 0 //当前最大值

   for i < len {
      j = i + 1
      curMaxPro = 0
      for j < len {
         if prices[j] > prices[i] {
            curMaxPro = prices[j] - prices[i]
            if rsMaxPro < curMaxPro {
               rsMaxPro = curMaxPro
            }
         }
         j += 1
      }

      i += 1
   }

   return rsMaxPro
}

2、图标法

通过图标发,可以得出,最大利润为波峰和波谷的差值。

func maxProfit(prices []int) int {
   var len int = len(prices)
   var i int = 1

   if len == 0 {
      return  0
   }

   var minPrice int = prices[0] //设置起点的价格
   var curMaxPro int = 0 //当前最大值

   for i < len {
      if minPrice > prices[i] {
         minPrice = prices[i]
      } else if prices[i] - minPrice > curMaxPro {
         curMaxPro = prices[i] - minPrice
      }

      i += 1
   }

   return curMaxPro
}