【力扣-每日一题】901. 股票价格跨度

暴力解法：

class StockSpanner {
private:
    vector<int> pri;
public:
    StockSpanner() {
        
    }
    
    int next(int price) {
        pri.emplace_back(price);
        int count=0;
        for(int i=pri.size()-1;i>=0;i--)
            {
                if(pri[i]<=price)
                    count++;
                else break;
            }
        return count;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

单调栈：

class StockSpanner {
private:
    stack<pair<int,int>> pri;   //单调栈
    int cur_day=-1; //当前天数
public:
    StockSpanner() {
        pri.emplace(-1,INT_MAX);//永远不会出栈，不会出现栈空
    }
    
    int next(int price) {
        cur_day++;//天数加一，stockSpanner对饮第0天
       //如果比当前这个数大，则一直出栈
       while(price>=pri.top().second){      //维护一个单调递减的栈
           pri.pop();
       }
       //如果当前这个数比栈顶大-出栈
       //如果当前这个数比栈顶小-出现截断，不能再连续-->计算天数，入栈
       int ans=cur_day-pri.top().first;
       pri.emplace(cur_day,price);
       return ans;
    }
};

/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28