题目链接

买卖股票的最佳时机

题目描述

image.png

实现代码

思路：本题主要是让我们选择股票买卖的两个时机，我们假设买股票是cur_buy，卖股票是在cur_sale，可以知道：

  1. cur_buy 在 cur_sale之前；
  2. cur_buy 小于 cur_sale；

同时进一步的思考可以知道：

  1. cur_buy可能是从开始遍历找到第一个最后递减的值，cur_buy则可能是从cur_buy下一个位置开始遍历找到第一个最后递增的值；这两者的差值可能是最终结果；
  2. 为什么说是可能，因为可能在cur_sale之后还是会存在这样的组合，结果比他们更大；

因此，我们需要维护这两个值，同时维护一个ans大值结果，经过一轮遍历找到所有这样的组合，同时只记录最大的ans，最终的ans即为结果

实现代码如下：

  1. class Solution:
  2.     def maxProfit(self, prices: List[int]) -> int:
  4.         n = len(prices)
  5.         if n == 1:
  6.             return 0
  7.         cur_buy = prices[0]
  8.         cur_sale = -1
  9.         ans = 0
  11.         first = True
  13.         for price in prices:
  15.             if first:
  16.                 first = False
  17.                 continue
  19.             if price < cur_buy:
  20.                 cur_buy = price
  21.                 if cur_sale == -1:
  22.                     continue
  23.                 cur_sale = -1
  24.                 continue
  25.             if price > cur_sale:
  26.                 cur_sale = price
  27.                 ans = max(cur_sale - cur_buy, ans)
  28.                 continue
  30.         return ans
  1. public class Solution {
  2.     public int maxProfit(int prices[]) {
  3.         int minprice = Integer.MAX_VALUE;
  4.         int maxprofit = 0;
  5.         for (int i = 0; i < prices.length; i++) {
  6.             if (prices[i] < minprice) {
  7.                 minprice = prices[i];
  8.             } else if (prices[i] - minprice > maxprofit) {
  9.                 maxprofit = prices[i] - minprice;
  10.             }
  11.         }
  12.         return maxprofit;
  13.     }
  14. }