901. 股票价格跨度

左手的ㄟ右手 2024-04-01 09:28 61阅读 0赞

问题描述：

> 编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。
> 
> 今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
> 
> 例如，如果未来7天股票的价格是 \[100, 80, 60, 70, 60, 75, 85\]，那么股票跨度将是 \[1, 1, 1, 2, 1,  
> 4, 6\]。

问题思路：

找到**股票价格小于或等于今天价格的最大连续日数** 等价于  
**找到股票价格大于自己的最近一天**

> 如果第 i 天的价格为 A\[i\]，第 j 天的价格为 A\[j\]，满足 i < j 且 A\[i\] <= A\[j\]，那么在第 j 天之后，第 i天不会是任何一天询问的答案。  
> 因为如果对于第 k, k > j 天而言，第 i 天是最近的一个大于今日价格的日子，但第 j 天出现在第 i天之后且价格不低于第 i 天，因此出现了矛盾。

所以考虑用**单调递减栈**来处理。  
每一次进行处理时，把价格小于等于自己的数据取出，因为它们不会是任何一天询问的答案。

比如这几天的价格为11 8 9 12 5 6 7  
栈的数据为：

11
    11 8   
    11 9 // 弹出8
    12 // 弹出9 11
    12 5
    12 6 // 弹出5

同时维护一个map，存放每天对应的股票跨度weight，每取出一个数累加weight，最后再加上一个自己，就是今天的股票跨度，最后把今天的数据存入。

Stack<Integer> prices;
    
        Map<Integer,Integer> weights;
    
        /**
         * 初始化一个单调递减栈，以及一个map存放栈元素对应的跨度weight
         */
        public StockSpanner() {
        
            prices = new Stack<>();
            weights = new HashMap<>();
        }
    
        public int next(int price) {
        
            // 初始化跨度，包括一个自己
            int weight = 1;
    
            // 如果栈非空，将所有比自己小/等于的栈元素取出，并且累加weight
    
            // peek 返回栈顶但不弹出 pop 返回栈顶且弹出
            while (!prices.empty() && prices.peek() <= price){
        
                int top = prices.pop();
                weight += weights.get(top);
            }
    
            prices.push(price);
            weights.put(price,weight);
            return weight;
        }

再考虑，一定要同时维护stack和map吗，价格和价格跨度其实可以用一个自定义对象同时维护，而且Deque双端队列，比Stack性能表现更好，于是修改代码

class StockSpanner {
        
     	Deque<Stock> deque;
    
        static class Stock{
        
    
            private int price;
            private int weight;
    
            public Stock(int price, int weight){
        
                this.price = price;
                this.weight = weight;
            }
        }
    
        public StockSpanner() {
        
            deque = new ArrayDeque<>();
        }
    
        public int next(int price) {
        
            int weight = 1;
            // 找到价格比自己大的
            while (!deque.isEmpty() && deque.peekLast().price <= price){
        
                weight += deque.removeLast().weight;
            }
            deque.addLast(new Stock(price,weight));
            return weight;
        }
    }

![在这里插入图片描述][19d7a5ffc8054b1ea809d9115e024e8d.png]

总结：  
往前走找第一个比自己 大 的元素，用单调递减的栈  
往前走找第一个比自己 小 的元素，用单调递增的栈

[19d7a5ffc8054b1ea809d9115e024e8d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/01/383d7058f3184ad587d993f539f8a988.png