大纲
题目
地址
https://leetcode.com/problems/best-time-to-buy-and-sell-stock/description/
内容
You are given an array prices where prices[i] is the price of a given stock on the ith day.
You want to maximize your profit by choosing a single day to buy one stock and choosing a different day in the future to sell that stock.
Return the maximum profit you can achieve from this transaction. If you cannot achieve any profit, return 0.
Example 1:
Input: prices = [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.
Note that buying on day 2 and selling on day 1 is not allowed because you must buy before you sell.
Example 2:
Input: prices = [7,6,4,3,1]
Output: 0
Explanation: In this case, no transactions are done and the max profit = 0.
Constraints:
- 1 <= prices.length <= 105
- 0 <= prices[i] <= 104
解题
这题就是要找到在一个区间中，计算一个值与后面最大值的差，然后找到最大的差。
一种直观的思路就是找到一个值后，去寻找它后面最大的值，然后将差保存起来。不停迭代这个过程，得到最大的差值。但是这个思路是O（n2），非常耗时。
实际我们在考虑这个问题时，需要抓住一个点：起始位置（目前的最小值）后如果小于该值的值，则它和后面出现的最大值的差就是最大差；如果出现了比它小的值，就要拿这个小的值向后去尝试。以此类推，可以得出最大的差值。这样它的复杂度就是O(n)。
#include <vector>
using namespace std;
class Solution {
public:
int maxProfit(vector<int>& prices) {
int minPrice = prices[0];
int maxProfit = 0;
for (int a: prices) {
if (minPrice > a) {
minPrice = a;
} else {
maxProfit = max(maxProfit, a - minPrice);
}
}
return maxProfit;
}
};
代码地址
https://github.com/f304646673/leetcode/tree/main/121-Best-Time-to-Buy-and-Sell-Stock/cplusplus
标签：Sell,sell,Buy,profit,maxProfit,121,int,prices,day From： https://blog.csdn.net/breaksoftware/article/details/142204685