更新121. 买卖股票的最佳时机

594Surefour · May 25, 2020 · 4083023 · 4083023
1 parent 1e5e922
commit 4083023
Showing 1 changed file with 47 additions and 52 deletions.
diff --git a/docs/Algorithm/Leetcode/Python/121._Best_Time_to_Buy_and_Sell_Stock.md b/docs/Algorithm/Leetcode/Python/121._Best_Time_to_Buy_and_Sell_Stock.md
@@ -1,83 +1,78 @@
 #  121. Best Time to Buy and Sell Stock
-**<font color=red>难度: 简单</font>**
+
+**<font color=green>难度: Easy</font>**
 
 ## 刷题内容
 
 > 原题连接
 
-* https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
+* https://leetcode.com/problems/best-time-to-buy-and-sell-stock
+* https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
 
 > 内容描述
 
 ```
-Say you have an array for which the ith element is the price of a given stock on day i.
+给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
+
+如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
 
-If you were only permitted to complete at most one transaction (i.e., buy one and sell one share of the stock), design an algorithm to find the maximum profit.
+注意：你不能在买入股票前卖出股票。
 
-Note that you cannot sell a stock before you buy one.
+示例 1:
 
-Example 1:
+输入: [7,1,5,3,6,4]
+输出: 5
+解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
+     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。
 
-Input: [7,1,5,3,6,4]
-Output: 5
-Explanation: Buy on day 2 (price = 1) and sell on day 5 (price = 6), profit = 6-1 = 5.
-             Not 7-1 = 6, as selling price needs to be larger than buying price.
-Example 2:
+示例 2:
 
-Input: [7,6,4,3,1]
-Output: 0
-Explanation: In this case, no transaction is done, i.e. max profit = 0.
+输入: [7,6,4,3,1]
+输出: 0
+解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。
 ```
 
 ## 解题方案
 
-
 > 思路1
 
-对于从第一天后的每一天，我们都假设昨天就已经卖掉了，那么现在我们可以看看**如果昨天卖可以赚的钱加上今天与昨天股票的价格差价**是否大于0，如果大于0就说明今天卖赚的更多，那么我们就还是先存下今天卖可以多赚的max_cur，继续往后看，如果小于0就还是坚持昨天可以赚的钱（即之前的max_cur）
-
-All the straight forward solution should work, but if the interviewer twists the question slightly 
-by giving the difference array of prices, Ex: for ```{1, 7, 4, 11}```, if he gives ```{0, 6, -3, 7}```, 
-you might end up being confused.
-
-Here, the logic is to calculate the difference ```(maxCur += prices[i] - prices[i-1])```
-of the original array, and find a contiguous subarray giving maximum profit. 
-If the difference falls below ```0```, reset it to zero.
-
-参考[Maximum subarray problem](https://en.wikipedia.org/wiki/Maximum_subarray_problem), 
-[Kadane's Algorithm](https://discuss.leetcode.com/topic/19853/kadane-s-algorithm-since-no-one-has-mentioned-about-this-so-far-in-case-if-interviewer-twists-the-input)
-
+1. 找到一个最低价格的位置，记录 index
+2. 找到一个最大卖出价格的位置，记录 利润
 
+```py
+class Solution:
+    def maxProfit(self, prices):
+        n = len(prices)
+        if n == 0: return 0
+
+        result = 0
+        minprice = prices[0]
+        for i in range(1, n):
+            minprice = min(prices[i], minprice)
+            result = max(prices[i] - minprice, result)
+        return result
 ```
-Why maxCur = Math.max(0, maxCur += prices[i] - prices[i-1]); ?
-
-Well, we can assume opt(i) as the max Profit you will get if you sell the stock at day i;
-
-We now face two situations:
 
-We hold a stock at day i, which means opt(i) = opt(i - 1) - prices[i - 1] + prices[i] (max Profit you can get if you sell stock at day(i-1) - money you lose if you buy the stock at day (i-1) + money you gain if you sell the stock at day i.
+> 思路2
 
-We do not hold a stock at day i, which means we cannot sell any stock at day i. In this case, money we can get at day i is 0;
+1. 初始化 dp，用于存放目录结果
+2. 找到最小值，计算当前最大的利润，存放到 dp中
+3. 找到 dp 以后一个元素，就是当前结果的最大值
 
-opt(i) is the best case of 1 and 2.
+```py
+class Solution:
+    def maxProfit(self, prices):
+        n = len(prices)
+        if n == 0: return 0
 
-So, opt(i) = Max{opt(i - 1) - prices[i - 1] + prices[i], 0}
-```
+        dp = [0] * n
+        minprice = prices[0] 
+        for i in range(1, n):
+            # 找到最小的值
+            minprice = min(minprice, prices[i])
+            dp[i] = max(dp[i - 1], prices[i] - minprice)
 
-```python
-class Solution(object):
-    def maxProfit(self, prices):
-        """
-        :type prices: List[int]
-        :rtype: int
-        """
-        if not prices or len(prices) == 0:
-            return 0
-        res, max_cur = 0, 0
-        for i in range(1, len(prices)):
-            max_cur = max(0, max_cur+prices[i]-prices[i-1]) # 如果今天卖相比于昨天卖能多赚，则今天卖，否则之前就卖了
-            res = max(res, max_cur)
-        return res
+        return dp[-1]
 ```