「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每日一题」——169. 多数元素
169. 多数元素 链接：https://leetcode-cn.com/problems/majority-element/难度：简单 题目 给定一个大小为 n 的数组，找到其中…
-
「LeetCode每日一题」——322. 零钱兑换
322. 零钱兑换 链接：https://leetcode-cn.com/problems/coin-change/难度：中等 题目 给定不同面额的硬币 coins 和一个总金额 …
-
「LeetCode每日一题」—— 46. 全排列
46. 全排列 链接：https://leetcode-cn.com/problems/permutations/难度：中等 题目 点击原文链接跳转查看题目 思路 这题算是一个基础…
-
「LeetCode每日一题」——LCCI. 01.06 字符串压缩
LCCI. 01.06 字符串压缩 链接：https://leetcode-cn.com/problems/compress-string-lcci/难度：简单 题目 字符串压缩。…
-
「LeetCode每日一题」——994. 腐烂的橘子
994. 腐烂的橘子 链接：https://leetcode-cn.com/problems/rotting-oranges/难度：简单 题目 在给定的网格中，每个单元格可以有以下…
-
「LeetCode每日一题」—— 199. 二叉树的右视图
199. 二叉树的右视图 链接：https://leetcode-cn.com/problems/binary-tree-right-side-view/难度：中等 题目 点击原文…
-
「LeetCode每日一题」—— LCCI.01.07. 旋转矩阵
LCCI.01.07. 旋转矩阵 题目链接：https://leetcode-cn.com/problems/rotate-matrix-lcci/难度：中等 题目 给你一幅由 N…
-
「LeetCode每日一题」——1160. 拼写单词
1160. 拼写单词 链接：https://leetcode-cn.com/problems/find-words-that-can-be-formed-by-characters…
-
「LeetCode每日一题」——1071. 字符串的最大公因子
1071. 字符串的最大公因子 链接：https://leetcode-cn.com/problems/greatest-common-divisor-of-strings/难度：…
-
「LeetCode每日一题」—— 56. 合并区间
56. 合并区间 链接：https://leetcode-cn.com/problems/merge-intervals/难度：中等 题目 给出一个区间的集合，请合并所有重叠的区间…
您必须登录才能发表评论。