广州市酒店网站设计dedecms 图片网站

题目描述

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。假设你可以在第 i 天买入并在第 j 天卖出股票（i ≤ j），设计一个算法来计算你所能获取的最大利润。注意你只能持有一股股票，并且你不能同时参与多笔交易（即在再次买入前必须卖出股票）。

示例

示例 1:

输入: prices = [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，可以获得最大利润，为 5。

示例 2:

输入: prices = [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

题解

这个问题可以通过一次遍历来解决。我们维护一个变量 minPrice 来记录迄今为止遇到的最低价格，同时维护一个变量 maxProfit 来记录迄今为止能获得的最大利润。

1. 初始化：minPrice 设置为第一个股票价格，maxProfit 设置为 0。
2. 遍历数组：从第二个价格开始遍历股票价格数组。
   ○ 对于每个价格，如果它小于 minPrice，则更新 minPrice。
   ○ 否则，计算当前利润（当前价格减去 minPrice），如果这个利润大于 maxProfit，则更新 maxProfit。
3. 返回结果：遍历结束后，maxProfit 就是能获得的最大利润。

代码实现

int maxProfit(vector<int>& prices) {if (prices.empty()) return 0;int minPrice = prices[0];int maxProfit = 0;for (int i = 1; i < prices.size(); i++) {if (prices[i] < minPrice) {minPrice = prices[i];} else {int profit = prices[i] - minPrice;if (profit > maxProfit) {maxProfit = profit;}}}return maxProfit;
}

复杂度分析

● 时间复杂度：O(n)，其中 n 是数组 prices 的长度。我们只需要遍历一次数组。
● 空间复杂度：O(1)，因为我们只使用了常数个额外变量。
这个算法的优势在于它的时间效率较高，只需要一次遍历即可找到最大利润，且不需要额外的存储空间。