02_买股票的最佳时机

# 解题思路1 超时 ❌
class Solution(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        解题思路1 比较笨的方法 双层遍历
        参数过大超出时间范围
        """
        # 初始化利润的最大值
        max_money = 0
        for i in range(len(prices)):
            for j in range(i + 1, len(prices)):
                if prices[j] > prices[i]:
                    if prices[j] - prices[i] > max_money:
                        max_money = prices[j] - prices[i]

        return max_money

# 解题思路2 超时 ❌


class Solution2(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        解题思路1 单层遍历 然后将这个值和右边的最大值比较
        """
        # 初始化利润的最大值
        max_money = 0
        for i in range(len(prices)):
            max_val = max(prices[i:])
            if max_val - prices[i] > max_money:
                max_money = max_val - prices[i]

        return max_money


# 解题思路3 遍历,总是关注最小值,发现值大就和目前感知到的最小值比 ✅ 用if 76ms 用max 48ms
class Solution3(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        # 初始化利润的最大值
        min_val = prices[0]
        max_money = 0

        for i in prices:
            if i <= min_val:
                min_val = i
            else:
                if i - min_val > max_money:
                    max_money = i - min_val
                # max_money = max(i - min_val, max_money)
        return max_money


# 思路3改进 不过思路3好理解
class Solution4(object):
    def maxProfit(self, prices):
        """
        :type prices: List[int]
        :rtype: int
        """
        if not prices:
            return 0
        # 初始化利润的最大值
        min_val = prices[0]
        max_money = 0

        for i in prices:
            min_val = min(i, min_val)
            max_money = max(i - min_val, max_money)
        return max_money


prices = [1, 2]
s = Solution()
s.maxProfit(prices)