目錄
1，題目描述
英文描述
中文描述
2，解題思路
基本思想
3，AC代碼
4，解題過程
第一博
第二搏
1，題目描述
英文描述
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 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.
中文描述
給定一個數組，它的第 i 個元素是一支給定股票第 i 天的價格。
如果你最多隻允許完成一筆交易（即買入和賣出一支股票一次），設計一個算法來計算你所能擷取的最大利潤。
注意：你不能在買入股票前賣出股票。
示例 1:
輸入: [7,1,5,3,6,4]
輸出: 5
解釋: 在第 2 天（股票價格 = 1）的時候買入，在第 5 天（股票價格 = 6）的時候賣出，最大利潤 = 6-1 = 5 。
注意利潤不能是 7-1 = 6, 因為賣出價格需要大于買入價格；同時，你不能在買入前賣出股票。
示例 2:
輸入: [7,6,4,3,1]
輸出: 0
解釋: 在這種情況下, 沒有交易完成, 是以最大利潤為 0。
來源：力扣（LeetCode）
連結：https://leetcode-cn.com/problems/best-time-to-buy-and-sell-stock
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。
2，解題思路
參考@力扣官方題解【121. 買賣股票的最佳時機】
基本思想
- minPrice維護目前周遊到的最小值（最低點）；
- 每到一個新的點，更新一次minPrice，并且利用ans = max(ans, prices[i] - minPrice) 更新ans；
就是這麼簡單。
3，AC代碼
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0, minPrice = INT_MAX;
for(int i = 0; i < prices.size(); ++i){
minPrice = min(minPrice, prices[i]);
ans = max(ans, prices[i] - minPrice);
}
return ans;
}
};
4，解題過程
第一博
O（N^2）的算法肯定都知道，雙重周遊，每對合理的位置都判斷一下。但是不用想，穩穩逾時。
于是換了一種思路，聲明兩個數組in和out分别記錄到位置 i（包括i）之前/之後的最小值/最大值，然後再次周遊一邊數組，将對應位置的值相減，更新結果；
class Solution {
public:
int maxProfit(vector<int>& prices) {
vector<int> in(prices.size()); // 記錄買入時各位置之前的最低價格
vector<int> out(prices.size()); // 記錄賣出時各位值之後的最高價格
if(prices.size() == 0) return 0; // 可能出現數組元素為空的情況
int ans = -1; // 初始為-1 用來辨別無滿足條件的解
in[0] = prices[0];
for(int i = 1; i < prices.size(); ++i) // 從前往後 更新各位置之前的最低價格
in[i] = min(in[i - 1], prices[i]);
out[prices.size() - 1] = prices.back();
for(int i = prices.size() - 2; i >= 0; --i) // 從後往前 更新各位置之後的最高價格
out[i] = max(out[i + 1], prices[i]);
for(int i = 0; i < prices.size(); i++) // 獲得最終結果
ans = max(ans, out[i] - in[i]);
if(ans < 0) return 0;
return ans;
}
};
第二搏
看了官方題解後，感覺自己┗( T﹏T )┛
為啥要來回周遊兩次數組呢？維持一個目前最小值minPrice，配合目前值prices[i]來更新ans不香嗎？
