#121. Best Time to Buy and Sell Stock
題目描述
給你一個陣列prices，prices[i]是股票第i天的價格。
請從陣列中選出一天買入股票，並且選擇未來的另外一天賣出股票來獲得最大的收益。
請回傳這筆買賣能獲得的最大收益，如果沒有辦法獲得任何收益，則回傳0。
限制條件
- 1 <= 陣列長度 <= 10^5
- 0 <= 價格 <= 10^4
- 不能在同一天同時買賣股票。
- 不能先賣後買。
解題思路
從陣列中挑出一筆買賣，這筆買賣為最大收益。
最大收益可以很直觀的理解為低買高賣，也就是只要找到最低點與最高點相減就會有最大的收益。
但同時要考慮到這是一個只能先買後賣的問題，當下決定的最低點不一定是整個陣列的最低點，就算找到最高點也不一定能獲得最高的收益。
因此這邊要計算出每一個當下最低點和最高點之間的收益，找到最大的那一筆。
public class Solution {
public int MaxProfit(int[] prices) {
//邊緣案例 Edge case
if(prices.Length<2) return 0;
//
int minPrice = 10001;
int maxProfit = 0;
for(int i=0;i<prices.Length;i++){
if(prices[i]<minPrice){
minPrice = prices[i];
}else if(prices[i]-minPrice>maxProfit){
maxProfit = prices[i]-minPrice;
}
}
return maxP>0?maxP:0;
}
}
複雜度分析：
- 時間複雜度：直到檢查最後一筆價格之前，都有可能存在更大的收益，因此要檢查完全部的價格，時間複雜度為O(n)。
- 空間複雜度：沒有使用到任何會增長的資料結構，空間複雜度為O(1)。