当前位置：首页 > news >正文

做营销网站建设app引流推广方法

news 2025/7/23 11:58:54

做营销网站建设,app引流推广方法,网站内容图片怎么做,国家网站集约化建设试点方案买卖股票的最佳时机问题描述给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你只能选择某一天买入股票，并选择未来的某一天卖出股票，设计一个算法来计算你所能获取的最大利润。限制条件： 只能进行一次交易&…

买卖股票的最佳时机

问题描述

给定一个数组 prices，其中 prices[i] 表示第 i 天的股票价格。你只能选择某一天买入股票，并选择未来的某一天卖出股票，设计一个算法来计算你所能获取的最大利润。

限制条件：
- 只能进行一次交易：也就是说，最多只能买入和卖出各一次。
- 买入必须在卖出之前：不能在买入之前卖出股票。
目标：返回可以获得的最大利润。如果无法获取任何利润，返回 0。

示例

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：5
解释：在第 2 天（价格为 1）买入，在第 5 天（价格为 6）卖出，利润为 6 - 1 = 5。

示例 2：

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

解题思路

为了求最大利润，我们需要在买入价格最低的时候买入，并在之后价格最高的时候卖出。然而，由于我们只能遍历一次数组，并且需要在买入之后才能卖出，因此我们需要一种高效的方法来计算最大利润。

核心思想：

维护一个当前为止的最低买入价格 minPrice。
计算当前价格与最低买入价格之间的差值，即当前可获得的利润 price - minPrice。
维护一个最大利润值 maxProfit，在遍历过程中更新它。

算法步骤

初始化：
- minPrice = Infinity：表示当前遇到的最低价格，初始为正无穷大。
- maxProfit = 0：表示当前计算的最大利润，初始为 0。
遍历价格数组：

对于每个价格 price，执行以下操作：
- 更新最低价格：
  - 如果 price < minPrice，则更新 minPrice = price。
- 计算当前利润并更新最大利润：
  - 计算当前利润 profit = price - minPrice。
  - 如果 profit > maxProfit，则更新 maxProfit = profit。
返回结果：
- 遍历完成后，maxProfit 即为所能获得的最大利润。

代码详解

function maxProfit(prices: number[]): number {let minPrice = Infinity; // 初始化最低价格为无穷大let maxProfit = 0;       // 初始化最大利润为 0for (let price of prices) {if (price < minPrice) {minPrice = price; // 更新最低价格} else if (price - minPrice > maxProfit) {maxProfit = price - minPrice; // 更新最大利润}}return maxProfit;
}

变量初始化：
- minPrice：用于记录当前为止的最低买入价格。
- maxProfit：用于记录当前为止的最大利润。
遍历数组：
```
for (let price of prices) {...
}
```
- 更新最低价格：
```
if (price < minPrice) {minPrice = price;
}
```
  - 如果当前价格比之前记录的最低价格还低，更新最低价格。
- 更新最大利润：
```
else if (price - minPrice > maxProfit) {maxProfit = price - minPrice;
}
```
  - 如果当前价格与最低价格的差值（利润）大于之前的最大利润，更新最大利润。
返回结果：
```
return maxProfit;
```
- 返回计算得到的最大利润。

示例演示

以示例 1 为例，prices = [7,1,5,3,6,4]：

初始状态：
- minPrice = Infinity
- maxProfit = 0
遍历过程：
1. price = 7：
  - 7 < Infinity，更新 minPrice = 7。
  - 没有更新 maxProfit，因为 price - minPrice = 0。
2. price = 1：
  - 1 < 7，更新 minPrice = 1。
  - 没有更新 maxProfit，因为 price - minPrice = 0。
3. price = 5：
  - 5 > 1，计算利润 5 - 1 = 4。
  - 4 > 0，更新 maxProfit = 4。
4. price = 3：
  - 3 > 1，计算利润 3 - 1 = 2。
  - 2 < 4，maxProfit 不变。
5. price = 6：
  - 6 > 1，计算利润 6 - 1 = 5。
  - 5 > 4，更新 maxProfit = 5。
6. price = 4：
  - 4 > 1，计算利润 4 - 1 = 3。
  - 3 < 5，maxProfit 不变。
结果：
- 最终 maxProfit = 5。

时间和空间复杂度分析

时间复杂度：O(n)，其中 n 是数组 prices 的长度。我们只需要遍历一次数组。
空间复杂度：O(1)，只使用了常数级别的额外空间。

边界情况处理

价格单调递减：
- 例如 prices = [7,6,4,3,1]，在这种情况下，无法获得正利润。
- 算法会始终更新 minPrice，但 maxProfit 保持为 0。
- 最终返回 0。
只有一个价格：
- 当 prices.length == 1 时，无法完成交易，利润为 0。

测试代码

function testMaxProfit() {const testCases = [{ prices: [7, 1, 5, 3, 6, 4], expected: 5 },{ prices: [7, 6, 4, 3, 1], expected: 0 },{ prices: [1, 2], expected: 1 },{ prices: [2, 4, 1], expected: 2 },{ prices: [3], expected: 0 },];for (let { prices, expected } of testCases) {const result = maxProfit(prices);console.assert(result === expected, `测试失败：输入 ${prices}，期望输出 ${expected}，实际输出 ${result}`);}console.log("所有测试用例通过！");
}testMaxProfit();