121 Best Time to Buy and Sell Stock 買(mǎi)賣(mài)股票的最佳時(shí)機(jī)
Description:
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 (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.
Example:
Example 1:
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:
Input: [7,6,4,3,1]
Output: 0
Explanation: In this case, no transaction is done, i.e. max profit = 0.
題目描述:
給定一個(gè)數(shù)組,它的第 i 個(gè)元素是一支給定股票第 i 天的價(jià)格。
如果你最多只允許完成一筆交易(即買(mǎi)入和賣(mài)出一支股票),設(shè)計(jì)一個(gè)算法來(lái)計(jì)算你所能獲取的最大利潤(rùn)。
注意你不能在買(mǎi)入股票前賣(mài)出股票幸冻。
示例:
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天(股票價(jià)格 = 1)的時(shí)候買(mǎi)入,在第 5 天(股票價(jià)格 = 6)的時(shí)候賣(mài)出青团,最大利潤(rùn) = 6-1 = 5 酸纲。
注意利潤(rùn)不能是 7-1 = 6, 因?yàn)橘u(mài)出價(jià)格需要大于買(mǎi)入價(jià)格兔毒。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒(méi)有交易完成, 所以最大利潤(rùn)為 0。
思路:
動(dòng)態(tài)規(guī)劃
前 i天的最大收益 = max[前 i天的價(jià)格 - min(前 i天價(jià)格)]
時(shí)間復(fù)雜度O(n), 空間復(fù)雜度O(1)
代碼:
C++:
class Solution
{
public:
int maxProfit(vector<int>& prices)
{
int result = 0, purchase = 1e5;
for (int i = 0; i < prices.size(); i++)
{
if (prices[i] < purchase) purchase = prices[i];
if (prices[i] - purchase > result) result = prices[i] - purchase;
}
return result;
}
};
Java:
class Solution {
public int maxProfit(int[] prices) {
int result = 0, purchase = (1 << 31) - 1;
for (int i = 0; i < prices.length; i++) {
if (prices[i] < purchase) purchase = prices[i];
if (prices[i] - purchase > result) result = prices[i] - purchase;
}
return result;
}
}
Python:
class Solution:
def maxProfit(self, prices: List[int]) -> int:
result, purchase = 0, (1 << 31) - 1
for price in prices:
purchase, result = min(price, purchase), max(price - purchase, result)
return result