「LeetCode每日一题」——121. 买卖股票的最佳时机
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。
思路
今天这个题，看着又像动态规划的题。
如果我们先不考虑动态规划，先试试枚举所有的情况，可能会超时，因为时间复杂度为O(n^2)，那如果这里我们只遍历一遍呢。如下图所示，我们遍历的时候带着最低点和最大差值往前走，遍历完了，最大的利润也有了。
为啥这种思路会起作用呢，这是因为这思路就是来自于动态规划。这里就不详细解释动态规划的解法了，后期在面试真题解析中会有这种题型的总结。代码见方案代码。
方案代码
解决方法：
class Solution:
def maxProfit(self, prices: List[int]) -> int:
inf = int(1e9)
maxprofit = 0
minprice = inf
for price in prices:
maxprofit = max(maxprofit, price - minprice)
minprice = min(price, minprice)
return maxprofit原创文章，作者：flypython，如若转载，请注明出处：http://flypython.com/algorithm/leetcode/213.html
微信扫一扫 
支付宝扫一扫 相关推荐
-
「LeetCode每日一题」——994. 腐烂的橘子
994. 腐烂的橘子 链接：https://leetcode-cn.com/problems/rotting-oranges/难度：简单 题目 在给定的网格中，每个单元格可以有以下…
-
「LeetCode每日一题」——543. 二叉树的直径
543. 二叉树的直径 链接：https://leetcode-cn.com/problems/diameter-of-binary-tree/难度：简单 题目 给定一棵二叉树，你…
-
「LeetCode每日一题」——1013. 将数组分成和相等的三个部分
1013. 将数组分成和相等的三个部分 链接：https://leetcode-cn.com/problems/partition-array-into-three-parts-w…
-
「LeetCode每日一题」——914. 卡牌分组
914. 卡牌分组 链接：https://leetcode-cn.com/problems/x-of-a-kind-in-a-deck-of-cards/难度：简单 题目 给定一副…
-
「LeetCode每日一题」—— 42. 接雨水
42. 接雨水 链接：https://leetcode-cn.com/problems/trapping-rain-water/难度：困难 题目 给定 n 个非负整数表示…
-
「LeetCode每日一题」—— 912. 排序数组
912. 排序数组 链接：https://leetcode-cn.com/problems/sort-an-array/难度：中等 题目 给你一个整数数组 nums，请你…
-
「LeetCode每日一题」——LCOF.62. 圆圈中最后剩下的数字
LCOF.62. 圆圈中最后剩下的数字 链接：https://leetcode-cn.com/problems/yuan-quan-zhong-zui-hou-sheng-xia-…
-
「LeetCode每日一题」——1071. 字符串的最大公因子
1071. 字符串的最大公因子 链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/难度：…
-
「LeetCode每日一题」—— 202. 快乐数
202. 快乐数 链接：https://leetcode-cn.com/problems/happy-number/难度：简单 题目 点击原文链接跳转查看题目 思路 今天是四月最后…
-
「LeetCode每日一题」——999. 车的可用捕获量
999. 车的可用捕获量 链接：https://leetcode-cn.com/problems/available-captures-for-rook/难度：简单 题目 在一个 …
您必须登录才能发表评论。