121、买卖股票的最佳时机
121、买卖股票的最佳时机
给定一个数组，它的第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。
第一种方法：暴力法
"""
直接遍历循环求解
"""
class Solution:
def maxProfit(self, prices):
n = len(prices)
if n <= 1:
return 0
max_profit = 0
for i in range(n):
for j in range(i, n):
if prices[i] < prices[j]:
profit = prices[j] - prices[i]
max_profit = max(profit, max_profit)
return max_profit
时间复杂度
O(n^2)，空间复杂度O(1)
从上面运行时间超时，放到pycharm中运行结果正确，因此想办法将时间降低。
第二种办法：动态规划
动态规划步骤，
1、明确
dp[i]表示的是什么关系2、找到
dp[i]与dp[i - 1]的关系得出状态转移方程3、确定初始条件，
dp[0]
在这里，1、dp[i]表示的是第i天的最大利润。2、dp[i]与dp[i - 1]的关系得出状态转移方程是dp[i] = max(dp[i-1], price - min_price)（也就是前一天的利润与今天的利润最大的一个）。3、dp[0]表达的是0。
代码实现如下：
class Solution:
def maxProfit(self, prices):
n = len(prices)
if n == 0 or n <= 1:return 0
dp = [0]*n #初始化dp[0] = 0了
min_price = prices[0]
for i in range(1, n):
min_price = min(min_price, pries[i]
dp[i] = max(dp[i - 1], prices[i] - min_price)
return dp[-1]
时间复杂度
O(n)，空间复杂度O(n)。
第三种办法：一次遍历解决（对动态规划的优化）
class Solution:
def maxProfit(self, prices):
if not prices or len(prices) < 2:return 0
min_price = float("inf")
max_profit = 0
for price in prices:
min_price = min(min_price, price)
max_profit = max(max_profit, price - min_price)
return max_profit
时间复杂度
O(n),空间复杂度O(1)
版权声明：本文为lishuntao原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。