每日一道算法之--买卖股票的最佳时机

动态规划

Word count: 562Reading time: 2 min

 2020/02/29   Share

买卖股票的最佳时机

力扣第121题：https://leetcode-cn.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 暴力方法

暴力方法简单容易理解，只是两次循环把所有的可能一一列举出来。然后在取其中的最大值

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        max_profit = 0
        for i in range(len(prices) - 1):
            for j in range(i + 1, len(prices)):
                profit = prices[j] - prices[i]
                max_profit = max(max_profit, profit)
        return max_profit

1.1 复杂度分析

时间复杂度:循环里嵌套另一个循环,所里时间复杂度为$$O(N^2)$$

空间复杂度:只使用了max_profit和profit两个变量,所以空间复杂度为$$O(1)$$

2 动态规划遍历一次

由题意不难理解,当前最大的收益就是你当前的价格减去之前的最小价格,所以定义一个变量min_price存储之前的最小值,在定义一个变量max_profit存储最大的收益值,便可以达到遍历一次

状态转移方程为dp[i] = max(dp[i-1]+diff[i], 0), dp[i])指以i元素结尾的子数组的最大和

class Solution:
    def maxProfit(self, prices: List[int]) -> int:
        min_price = float('inf')
        max_profit = 0
        for i in range(len(prices)):
            min_price = min(prices[i], min_price)
            max_profit = max(max_profit, prices[i]-min_price)
        return max_profit

2.1 复杂度分析

时间复杂度:遍历了一次数组,所以时间复杂度为$$O(N)$$

空间复杂度:只使用了min_price和max_profit两个变量,所以空间复杂度为$$O(1)$$

Author：liangweijiang

原文链接：https://liangweijiang.github.io/2020/02/29/algorithm-121/

发表日期：February 29th 2020, 3:25:08 pm

更新日期：March 2nd 2020, 6:29:59 pm

Next Post

每日一道算法之--无重复的最长的子字符串
Previous Post

DRF源码解析6--权限组件的封装和初始化

CATALOG

1. 买卖股票的最佳时机
1. 1.1. 1 暴力方法
  1. 1.1.1. 1.1 复杂度分析
2. 1.2. 2 动态规划遍历一次
  1. 1.2.1. 2.1 复杂度分析

