首页 > itarticle > 121. best time to buy and sell stock

121. best time to buy and sell stock

admin 1月 30, 2021 0

Description

Difficulty: Easy

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 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

In this case, no transaction is done, i.e. max profit = 0.

给出一数组，代表每天的股价。要求只能买卖一次，求最大利润。

Solution

实际上是求数组中后面的数与前面的数的最大差值。
最简单的方法自然是两个循环，但是时间复杂度为 O(n^2)，很不理想。

思路：由于在每个单调区间中对答案有意义的元素只有区间两端的值而已。
因此构建两个新数组，分别只包含每个单调区间的最大值与最小值。
之后，针对最小值数组中每个元素，找最大值数组相应位置及之后的最大元素即可算出最大差值（利润）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
 
class (object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        max_profit = 0
    
        if len(prices) == 2:
            return max(prices[1] - prices[0], 0)
    
        elif len(prices) > 2:
            low = prices[0]
            high = prices[0]
            profit = 0
            list_low = [prices[0]]
            list_high = []
            up = True
        
            for i in xrange(len(prices) - 1):
                if prices[i + 1] >= prices[i]:  
                    high = prices[i + 1]
                    if up == False:
                        low = prices[i]
                        list_low.append(low)
                        up = True
                elif prices[i + 1] < prices[i]:  # going down
                    low = prices[i + 1]
                    if up == True:
                        high = prices[i]
                        list_high.append(high)
                        up = False
            if len(list_high) < len(list_low):
                list_high.append(prices[-1])
    
            for j in xrange(len(list_low)):
                max_profit = max(max_profit, max(list_high[j:]) - list_low[j])
        return max_profit
微海报分享

近期文章

近期评论

标签

热门

文章归档

分类目录

功能