【leetcode刷题】2019/3/7 T13-买卖股票的最佳时机
【leetcode刷题】2019/3/7 T13-买卖股票的最佳时机
这是木又陪伴你的第21天
今天分享leetcode第13篇文章，也是leetcode第121题—买卖股票的最佳时机（Best Time to Buy and Sell Stock），地址是：https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
【英文题目】（学习英语的同时，更能理解题意哟~）
Say you have an array for which the i^th element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Note that you cannot sell a stock before you buy one.
Example 1:
Input: [7,1,5,3,6,4]
Output: 5
Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
Not 7-1 = 6, as selling price needs to be larger than buying price.
Example 2:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
【中文题目】
给定一个数组，它的第 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。
【思路】
这道题最直接的想法是：暴力破解，两层循环，计算所有的差价，返回最大值。
比如，对于数组[4, 2, 3, 1, 5 , 6]，计算2-4, 3-4, 1-4, 5-4, 6-4, 3-2, 1-2, 5-2, …, 6-1, 6-5，最终得到最大值6-1=5
那么问题来了，有没有可以省略的步骤呢？
当我们找到更小的买入价，以前的买入价还需要计算吗？比如计算了5-2，还需要计算5-4吗？
当然不用！
不可能卖出价相同的情况下，买入价更小，反而赚得更少。
那么我们可以用一个变量min0来存储当前位置股票最低价，这样，当前最多赚钱max(0, 当前价-min0)
该算法的时间复杂度为O(n)
【代码】
python版本
class Solution(object):
def maxProfit(self, prices):
"""
:type prices: List[int]
:rtype: int
"""
if len(prices) < 1:
return 0
min0 = prices[0]
res = 0
for p in prices[1:]:
# 价格更低
if p < min0:
min0 = p
# 赚得更多
if p - min0 > res:
res = p - min0
return res
C++版本
class Solution {
public:
int maxProfit(vector<int>& prices) {
if(prices.size() < 1)
return 0;
int min = prices[0];
int res = 0;
for(int i=1; i < prices.size(); i++){
// 价格更低
if(prices[i] < min)
min = prices[i];
// 赚得更多
if(prices[i] - min > res)
res = prices[i] - min;
}
return res;
}
};
哈哈哈，最近股票大火，这题真应景~
上一篇文章：
T12-搜索旋转排序数组II
给我好看