股票收益问题

在本教程中，我们将编写股票跨度问题的 Python 程序。这是一个非常流行的编程问题，经常出现在技术面试中。股票跨度问题是一项金融挑战，涉及分析特定股票的 N 天日价格报价系列。目标是确定该股票在 N 天内的跨度。给定日期 i 的跨度 Si 表示当前日期之前的连续最大天数，其中股票价格低于或等于给定日期当天的价格。

示例 -

输入： N = 7, 价格 = [100 80 60 70 60 75 85]

输出 1 1 1 2 1 4 6

解释： 遍历给定输入，100 的跨度将是 1，80 小于 100，所以跨度是 1，60 小于 80，所以跨度是 1，70 大于 60，所以跨度是 2，依此类推。因此，输出将是 1 1 1 2 1 4 6。

输入： N = 6, 价格 = [10 4 5 90 120 80]

输出 1 1 2 4 5 1

解释： 遍历给定输入，10 的跨度将是 1，4 小于 10，所以跨度将是 1，5 大于 4，所以跨度将是 2，依此类推。因此，输出将是 1 1 2 4 5 1。

为了解决这个问题，我们将使用朴素方法

解决方案 -

首先，我们使用朴素方法。为了解决股票跨度问题，我们可以遍历输入的价格数组。对于每个被访问的元素，我们迭代其左侧的元素，并增加当前元素的跨度值，只要左侧的元素小于或等于它。

示例 -

输出

[1, 1, 2, 4, 5, 1]

解释 -

在上面的代码中，我们定义了 getSpan() 函数，该函数计算给定价格数组的跨度值。

1. 初始化一个空的 S 数组，值为 None，它将存储跨度值。
2. 将 S 的第一个元素赋值为 1，因为第一天的跨度值总是 1。
3. 从第二个元素（i = 1）到最后一个元素（n-1）遍历价格数组。
4. 将当前天的跨度值（S[i]）初始化为 1。
5. 初始化一个变量 j 为 i - 1，表示前一天的索引。
6. 进入一个 while 循环，该循环一直持续到 j 大于或等于 0 并且当前天的价格（price[i]）大于或等于前一天的价格（price[j]）。
7. 在 while 循环内，将当前天的跨度值（S[i]）加 1，并将 j 减 1 以移到前一天。
8. 一旦 while 循环退出，当前天的跨度值（S[i]）就已计算出来。
9. 对剩余的天数重复步骤 5-8。
10. 返回包含跨度值的数组 S。

上述代码的时间复杂度为 O(n^2)，辅助空间为 O(n)。

方法 2：使用栈

在此方法中，我们首先创建一个空的整型栈并推入 0。现在，我们将第 1 天的默认值设置为 1，然后遍历其余的天数。当栈不为空且 st.top 的价格小于或等于当前天的价格时，弹出顶部值。现在，如果栈为空，则将当前天的值分配为 i+1，否则等于 i - st.top。将当前天推入栈并打印结果。让我们来理解下面的例子。

注意 - 当当前股票价格和前一天的股票价格相同时，我们不会从栈中弹出

示例 -

输出

[1, 1, 2, 4, 5, 1, 0]

解释 -

在上面的代码中，我们定义了 getSpan() 函数，该函数接受两个参数：price（股票价格列表）和 S（在代码中未使用，应删除）。

1. 将 n 赋值给价格列表的长度。然后我们使用列表初始化一个空的栈 st。
2. 将第一个元素 (0) 推入栈 st 作为起始点。
3. 创建一个长度为 n+1 的空列表 S。此列表将存储每天的股票跨度。
4. S 的第一个元素被赋值为 1，因为第一天没有可以与之比较的前一天。
5. for 循环在 1 到 n-1 的范围内迭代，代表从第二天到最后一天的天数。
6. 在循环内部，使用 while 循环检查栈是否不为空，并且栈顶的价格（由 st[-1] 索引）是否小于或等于当前天的价格（price[i]）。
7. 如果条件为真，则表示前几天的股票价格小于或等于当前天的价格。因此，我们从栈中弹出顶部元素，直到条件变为假。
8. while 循环结束后，S[i] 被赋值为 i + 1（如果栈为空，即所有前几天的股票价格都较小）或 (i - st[-1])（当前天的索引与栈顶元素的索引之间的差值），如果栈不为空。
9. 将索引 i 推入栈 st。
10. 循环结束后，返回股票跨度列表 S。

此方法的时​​间复杂度为 O(N)，辅助空间为 O(N)。

方法 3：使用动态规划

在此方法中，我们将存储每个索引的值，并使用前一个值计算下一个索引的值。现在，我们将检查前一个元素的值，如果当前元素的值大于前一个元素。我们将前一个值加到当前索引中，并检查 (前一个索引 - 前一个索引的值) 并重复检查条件。让我们来理解下面的例子。

示例 -

输出

[1, 1, 2, 4, 5, 1, 0]

解释 -

在上面的代码中，我们创建了 getSpan() 函数，该函数接受两个参数：price（股票价格列表）和 S（最初为空列表，但将用于存储跨度）。

1. 我们获取价格列表的长度 n。
2. 然后我们创建一个长度为 n+1 的新列表 S，所有元素都初始化为 0。此列表将存储跨度。
3. S 的第一个元素设置为 1，表示第一天的跨度始终为 1。
4. 从索引 1 到索引 n-1（不包括第一个和最后一个元素）开始一个循环。
5. 在循环内部，初始化一个计数器变量为 1。
6. 启动一个 while 循环来计算当前天的跨度。条件检查是否有前一天（即 i-counter 不为负）并且当前天的价格是否大于或等于前一天的价格（price[i] >= price[i - counter]）。
7. 如果条件满足，计数器将增加 S[i - counter] 的值。这样做是为了跳过已经计算出跨度的天数。
8. 一旦 while 循环结束，计算出的跨度（计数器）就被赋值给 S[i]。
9. 循环结束后，函数返回 S 列表，其中包含每天的跨度。

方法 4：使用两个栈

在此方法中，我们将使用两个栈，一个栈存储实际的股票价格，而另一个栈是临时栈。让我们来理解下面的例子。

示例 -

输出

[1, 1, 2, 4, 5, 1]

此方法的时​​间复杂度为 O(N)，辅助空间为 O(N)。

结论

在本教程中，我们讨论了解决股票跨度问题的各种方法。