901. 股票价格跨度

怼烎@ 2022-11-26 12:00 211阅读 0赞

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

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 \[100, 80, 60, 70, 60, 75, 85\]，那么股票跨度将是 \[1, 1, 1, 2, 1, 4, 6\]。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70_pic_center]

提示：

调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。  
每个测试用例最多可以调用 10000 次 StockSpanner.next。  
在所有测试用例中，最多调用 150000 次 StockSpanner.next。  
此问题的总时间限制减少了 50%。

来源：力扣（LeetCode）  
链接：[添加链接描述][Link 1]  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

想到KMP算法的next数组， 搞了一个pre数组记录每个价格pre多少个，每次加入新的数就通过pre数组寻找并更新pre数组。  
100 80 60 70 60 75 85  
1 1 1 2 1 4  
加入85时，创建计数器count=1，index设为75的下标5，85与75比较，index更新为5-4=1，count+=4，85再和80比较，，index更新为1-1=0，count+=1，85再和100比较，结束，pre\[6\]=count=6。

class StockSpanner {
        
    public:
        vector<int> pre;
        vector<int> vprice;
    
        StockSpanner() {
        
            while(!pre.empty()) pre.pop_back();
            while(!vprice.empty()) vprice.pop_back();
        }
        
        int next(int price) {
        
            vprice.push_back(price);
            int index = vprice.size() - 2;
            int temp = 1;
            int count = 1;
            while(index >= 0 && price >= vprice[index]) {
        
                temp = pre[index];
                count += temp;
                index = index - temp;
            }
            pre.push_back(count);
    
            return count;
        }
    };
    
    /**
     * Your StockSpanner object will be instantiated and called as such:
     * StockSpanner* obj = new StockSpanner();
     * int param_1 = obj->next(price);
     */

官方题解：单调栈

class StockSpanner {
        
    public:
        stack<int> s;
        stack<int> weight;
    
        StockSpanner() {
        
            while(!s.empty()) s.pop();
            while(!weight.empty()) weight.pop();
        }
        
        int next(int price) {
        
            if(s.empty()) {
        
                s.push(price);
                weight.push(1);
                return 1;
            }
            int count = 1;
            while(!s.empty() && price >= s.top()){
        
                s.pop();
                count+=weight.top();
                weight.pop();
            }
    
            s.push(price);
            weight.push(count);
    
            return count;
        }
    };
    
    /**
     * Your StockSpanner object will be instantiated and called as such:
     * StockSpanner* obj = new StockSpanner();
     * int param_1 = obj->next(price);
     */

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2x1amlhbjIzMw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/7646230d0d18488384b0fa4f9c35b8e4.png
[Link 1]: https://leetcode-cn.com/problems/online-stock-span