萌新刷题（十三）买卖股票的最佳时机

小歪

发布于 2018-04-04 14:44:11

7740

发布于 2018-04-04 14:44:11

文章被收录于专栏：Python爬虫与算法进阶

题目

假设有一个数组，它的第i个元素是一支给定的股票在第i天的价格。如果你最多只允许完成一次交易(例如,一次买卖股票),设计一个算法来找出最大利润。

样例

给出一个数组样例 [3,2,3,1,2], 返回 1

链接 Best Time to Buy and Sell Stock、Best Time to Buy and Sell Stock

题解

最多只允许进行一次交易，显然我们只需要把波谷和波峰分别找出来就好了。但是这样的话问题又来了，有多个波峰和波谷时怎么办？——找出差值最大的一对波谷和波峰。故需要引入一个索引用于记录当前的波谷，结果即为当前索引值减去波谷的值。

Python

class Solution:
    """
    @param prices: Given an integer array
    @return: Maximum profit
    """
    def maxProfit(self, prices):
        if prices is None or len(prices) <= 1:     
                return 0

        profit = 0
        cur_price_min = 2**31 - 1
        for price in prices:
            profit = max(profit, price - cur_price_min)
            cur_price_min = min(cur_price_min, price)  
                  
        return profit

总耗时: 289 ms

在leetcode上找到的更多解法

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if len(prices) == 0 or len(prices) == 1:  
            return 0

        MAX = 0

        start = prices[0]     
            
        for price in prices:    
            if price - start > MAX:
                MAX = price - start   
            if price < start :
                start = price
        
        return MAX

总耗时: 303 ms

class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        result = 0
        for i, price in enumerate(prices):   
             if i == 0:
                low = price
            low = min(price, low)
            result = max(price-low, result)        
        return result

总耗时: 239 ms

下面是小姐姐