刷题第一次断交

柔光的暖阳◎ 2022-09-03 05:25 137阅读 0赞

[121. 买卖股票的最佳时机][121.]

难度简单1761

给定一个数组 `prices` ，它的第 `i` 个元素 `prices[i]` 表示一支给定股票第 `i` 天的价格。

你只能选择 **某一天** 买入这只股票，并选择在 **未来的某一个不同的日子** 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 `0` 。

**示例 1：**

输入：[7,1,5,3,6,4]
    输出：5
    解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
         注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

**示例 2：**

输入：prices = [7,6,4,3,1]
    输出：0
    解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

**提示：**

*  `1 <= prices.length <= 105`
 *  `0 <= prices[i] <= 104`
 *      class Solution(object):
            def maxProfit(self,prices):
                """
                最大利润即数组中任意两个数字的最大差值，且大的数字必须在小的数字之后
                公式：i、j为日期且i < j，则最大利润为寻找max(prices[j] - prices[i])
                :param prices: List[int]
                :return: int
                暴力解法
                """
                max_profit=0
                n=len(prices)
                for i in range(n):
                    for j in range(i+1,n):
                        max_profit=max(max_profit,prices[j]-prices[i])
        
                return  max_profit
        
        
        
        
        class Solution(object):
            def maxProfit(self,prices):
                max_profit=0
                min_price=10**4+1
                for p in prices:
                    max_profit=max(max_profit,p-min_price)
                    min_price=min(min_price,p)
                return max_profit
        
        
        class Solution(object):
            def maxProfit(self,prices):
                #动态规划解法
                max_profit=0
                for i in range(1,len(prices)):
                    if prices[i]>prices[i-1]:
                        max_profit=max(max_profit,prices[i]-prices[i-1])
                        prices[i]=prices[i-1]
        
                return max_profit
        
        
        class Solution(object):
            def maxProfit(self,prices):
                min_price=prices[0]
                profit=0
                for current_price in prices[1:]:
                    min_price=min(min_price,current_price)
                    profit=max(profit,current_price-min_price)
                return  profit

[121.]: https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock/