DEV Community
·
🚀 解决股票跨度问题 - 我的思考过程与方法
💡
原文英文，约600词，阅读约需3分钟。
📝
内容提要
给定每日股票价格，计算每一天的价格跨度。跨度定义为在第i天之前（包括第i天）连续价格小于等于第i天价格的天数。通过优化栈存储价格和计数，实现O(n)复杂度，显著提高效率。
🎯
关键要点
- 给定每日股票价格，计算每一天的价格跨度。
- 价格跨度定义为在第i天之前（包括第i天）连续价格小于等于第i天价格的天数。
- 初始尝试使用栈存储价格，但复制栈导致O(n²)复杂度，效率低下。
- 第二次尝试使用双指针方法，但在最坏情况下仍然是O(n²)。
- 最终优化的栈方法通过存储价格和计数的对来实现O(n)复杂度。
- 每个元素只处理一次，显著提高了效率。
- 关键学习包括避免冗余操作、智能存储有用数据和有效利用数据结构。
➡️
