单调栈且O(N)
2024-11-11 19:15:21
发布于:湖南
7阅读
0回复
0点赞
对于每个价格,计算它作为最大值和最小值的贡献。
使用两个单调栈分别记录价格作为最大值和最小值时的左右边界。
对于每个价格,计算它作为最大值和最小值时的贡献并累加到总波幅之和中。
时间复杂度:O(N),因为每个价格只会进出单调栈一次。
空间复杂度:O(N),用于存储单调栈和边界信息。
全部评论 1
当前的算法时间复杂度是 O(N) ,已经是线性的最优解。除非有特定的硬件优化或并行计算,否则很难再提高性能。
1周前 来自 湖南
0
有帮助,赞一个