LeetCode 121 Best Time to Buy and Sell Stock
题目分析
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/
暴力遍历法
遍历所有买卖可能，O(n^2) 时间复杂度。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
for(int i = 0; i < prices.size(); i++) {
for (int j = i + 1; j < prices.size(); j++) {
ans = max(ans, prices[j] - prices[i]);
}
}
return ans;
}
};
TLE 了。
只遍历出售价格
我们遍历所有价格，使其轮流作为出售价格。 对于每一个出售价格，其最佳的买入价格即其之前最低的那个价格，因此我们完全可以 one pass 解决问题。
时间复杂度 O(n)。
class Solution {
public:
int maxProfit(vector<int>& prices) {
int ans = 0;
int buy = prices[0];
for(int i = 1; i < prices.size(); i++) {
// calculate profit based on current sell price
ans = max(ans, prices[i] - buy);
// update new lower buy price
buy = min(buy, prices[i]);
}
return ans;
}
};