股票价格上涨等待天数 - 算法题解

股票价格上涨等待天数 - 算法题解

题目描述： 给定某只股票连续N天的价格列表stockPrices，其中stockPrices[i]表示股票某天的价格，请生成一个新列表，对应位置输出为：要想等到股票价格上涨，至少需要等待的天数，如果股票价格不上涨，对应位置输出为0。

输入： 第一行 表示第二行元素的个数N 第二行 为用空格隔开的整数，表示每天股票的价格，其中0<N<=1000000，每天股票价格为正整数

输出： 输出为用空格分隔的长度为N的列表，对应位置为：要想等到股票价格上涨，至少需要等待的天数

样例1： 输入: 5 33 34 14 12 16 输出：1 0 2 1 0

解题思路：

1. 创建一个长度为N的结果列表result，初始值都为0。
2. 从第二天开始遍历股票价格列表stockPrices，将当前价格与前一天的价格进行比较。
3. 如果当前价格大于前一天的价格，则说明股票价格上涨，将对应位置的结果列表result的值设为1。
4. 如果当前价格小于等于前一天的价格，则说明股票价格没有上涨，将对应位置的结果列表result的值加1。
5. 返回结果列表result。

时间复杂度分析： 遍历股票价格列表需要O(N)的时间，其中N为股票价格列表的长度。

空间复杂度分析： 需要一个长度为N的结果列表result，空间复杂度为O(N)。

关键代码如下所示：

def stock_prices(stockPrices):
    N = len(stockPrices)
    result = [0] * N
    for i in range(1, N):
        if stockPrices[i] > stockPrices[i-1]:
            result[i] = 1
        else:
            result[i] = result[i-1] + 1
    return result

# 测试样例
stockPrices = [33, 34, 14, 12, 16]
print(stock_prices(stockPrices))

代码解释：

1. stock_prices(stockPrices) 函数接受一个股票价格列表 stockPrices 作为参数。
2. 使用 len(stockPrices) 获取股票价格列表的长度 N。
3. 初始化一个长度为 N 的列表 result，并将其所有元素都设置为 0。
4. 使用 for 循环遍历 stockPrices 列表，从第二个元素开始 (索引为 1)。
5. 在循环中，比较当前元素 stockPrices[i] 和前一个元素 stockPrices[i-1]。
6. 如果当前元素大于前一个元素，则说明股票价格上涨，将对应位置的 result[i] 设为 1。
7. 否则，说明股票价格没有上涨，将对应位置的 result[i] 设为 result[i-1] + 1。
8. 最后，返回结果列表 result。

测试样例解释：

stockPrices = [33, 34, 14, 12, 16]

在这个例子中，stockPrices 列表表示 5 天的股票价格。程序将会输出 [1, 0, 2, 1, 0]，表示：

• 第一天的股票价格为 33，第二天为 34，股票价格上涨，等待天数为 1。
• 第二天股票价格为 34，第三天为 14，股票价格下降，等待天数为 0。
• 第三天股票价格为 14，第四天为 12，股票价格下降，等待天数为 2。
• 第四天股票价格为 12，第五天为 16，股票价格上涨，等待天数为 1。
• 第五天股票价格为 16，没有后续价格，等待天数为 0。

希望以上解释能够帮助您理解这道算法题。如果您还有其他问题，请随时提问。