算法题股票价格跨度-编程实验室

股票价格跨度

问题描述

编写一个StockSpanner类，它收集某些股票的每日收盘价，并返回当日价格的跨度。

价格跨度：今天价格大于或等于过去连续x天价格的天数（包括今天）。

具体来说，如果prices = [100,80,60,70,60,75,85]，那么spans = [1,1,1,2,1,4,6]。

示例：

StockSpannerstockSpanner=newStockSpanner();stockSpanner.next(100);// 返回 1stockSpanner.next(80);// 返回 1stockSpanner.next(60);// 返回 1stockSpanner.next(70);// 返回 2 (70 >= 60)stockSpanner.next(60);// 返回 1stockSpanner.next(75);// 返回 4 (75 >= 60, 70, 60)stockSpanner.next(85);// 返回 6 (85 >= 75, 60, 70, 60, 80)

算法思路

单调栈：

核心思想：
- 维护一个单调递减栈，存储(price, span)对
- 当新价格到来时，弹出所有小于等于当前价格的元素
- 当前跨度 = 弹出元素的跨度之和 + 1

代码实现

方法一：单调栈

importjava.util.*;classStockSpanner{/** * 股票价格跨度计算器 * * 核心数据结构：单调递减栈 * 栈中存储 (price, span) 对 */privateDeque<int[]>stack;// int[0] = price, int[1] = spanpublicStockSpanner(){stack=newArrayDeque<>();}/** * 计算当前价格的跨度 * * 时间复杂度: O(1) * 空间复杂度: O(n) * * @param price 当前股票价格 * @return 价格跨度 */publicintnext(intprice){intspan=1;// 弹出所有小于等于当前价格的元素while(!stack.isEmpty()&&stack.peek()[0]<=price){span+=stack.pop()[1];}// 将当前价格和跨度压入栈stack.push(newint[]{price,span});returnspan;}}

方法二：使用两个栈

classStockSpanner{// 分别存储价格和跨度privateStack<Integer>prices;privateStack<Integer>spans;publicStockSpanner(){prices=newStack<>();spans=newStack<>();}publicintnext(intprice){intspan=1;// 弹出所有小于等于当前价格的价格while(!prices.isEmpty()&&prices.peek()<=price){prices.pop();span+=spans.pop();}prices.push(price);spans.push(span);returnspan;}}

算法分析

时间复杂度：O(1)
- 每个元素最多被压入和弹出一次
- n 次操作的总时间复杂度为 O(n)
- 平均每次操作 O(1)
空间复杂度：O(n)
- 最坏情况下栈中存储所有价格（严格递减序列）
- 平均情况下空间使用较少

算法过程

1：prices = [100,80,60,70,60,75,85]

初始: stack = [] next(100): - stack为空，span = 1 - stack = [(100,1)] - 返回 1 next(80): - 80 < 100，不弹出 - span = 1 - stack = [(100,1), (80,1)] - 返回 1 next(60): - 60 < 80，不弹出 - span = 1 - stack = [(100,1), (80,1), (60,1)] - 返回 1 next(70): - 70 > 60，弹出(60,1)，span = 1 + 1 = 2 - 70 < 80，停止 - stack = [(100,1), (80,1), (70,2)] - 返回 2 next(60): - 60 < 70，不弹出 - span = 1 - stack = [(100,1), (80,1), (70,2), (60,1)] - 返回 1 next(75): - 75 > 60，弹出(60,1)，span = 1 + 1 = 2 - 75 > 70，弹出(70,2)，span = 2 + 2 = 4 - 75 < 80，停止 - stack = [(100,1), (80,1), (75,4)] - 返回 4 next(85): - 85 > 75，弹出(75,4)，span = 1 + 4 = 5 - 85 > 80，弹出(80,1)，span = 5 + 1 = 6 - 85 < 100，停止 - stack = [(100,1), (85,6)] - 返回 6

测试用例

importjava.util.*;publicclassTest{publicstaticvoidmain(String[]args){// 测试用例1：标准示例StockSpannerspanner1=newStockSpanner();System.out.println("Test 1:");System.out.println("100: "+spanner1.next(100));// 1System.out.println("80: "+spanner1.next(80));// 1System.out.println("60: "+spanner1.next(60));// 1System.out.println("70: "+spanner1.next(70));// 2System.out.println("60: "+spanner1.next(60));// 1System.out.println("75: "+spanner1.next(75));// 4System.out.println("85: "+spanner1.next(85));// 6// 测试用例2：严格递增序列StockSpannerspanner2=newStockSpanner();System.out.println("10: "+spanner2.next(10));// 1System.out.println("20: "+spanner2.next(20));// 2System.out.println("30: "+spanner2.next(30));// 3System.out.println("40: "+spanner2.next(40));// 4// 测试用例3：严格递减序列StockSpannerspanner3=newStockSpanner();System.out.println("40: "+spanner3.next(40));// 1System.out.println("30: "+spanner3.next(30));// 1System.out.println("20: "+spanner3.next(20));// 1System.out.println("10: "+spanner3.next(10));// 1// 测试用例4：所有相同价格StockSpannerspanner4=newStockSpanner();System.out.println("50: "+spanner4.next(50));// 1System.out.println("50: "+spanner4.next(50));// 2System.out.println("50: "+spanner4.next(50));// 3System.out.println("50: "+spanner4.next(50));// 4// 测试用例5：单个价格StockSpannerspanner5=newStockSpanner();System.out.println("100: "+spanner5.next(100));// 1// 测试用例6：大数值StockSpannerspanner6=newStockSpanner();System.out.println("1000000: "+spanner6.next(1000000));// 1System.out.println("500000: "+spanner6.next(500000));// 1System.out.println("750000: "+spanner6.next(750000));// 2// 测试用例7：复杂StockSpannerspanner7=newStockSpanner();int[]prices={29,91,62,76,51};for(intprice:prices){System.out.println(price+": "+spanner7.next(price));}// 测试用例8：峰值StockSpannerspanner8=newStockSpanner();int[]prices2={10,20,30,40,30,20,10,50};for(intprice:prices2){System.out.println(price+": "+spanner8.next(price));}}}