【力扣每日一题】2023.10.7 股票价格跨度

目录

题目：

示例：

分析：

代码：

---

题目：

示例：

分析：

给我们一个数组表示不同时间的股票的价格，要我们按照顺序返回每天的股票价格跨度，价格跨度就是股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

实际上就是要我们找出数组中每个元素的上一个更大元素。

这类题目我们使用单调栈来解决，我们使单调栈内的元素（股票价格）保持单调递减，每次我们将新一天的股票价格塞进单调栈之前，我们都把价格小于新价格的元素从栈中弹出，直到栈顶元素大于新价格，那么当天的价格跨度就等于从今天到栈顶元素那天的时间差。

在塞入第一天的价格信息时，栈内是空的，我们很容易对空栈进行操作，所以我们可以在一开始塞入一个哨兵节点，也就是一个无穷大的值，这样在比较价格的时候就不可能将这个节点从栈中弹出了。

因为我们还需要记录不同价格所在的时间，所以存入栈的元素需要存放两个数，一个是价格，一个是时间，可以用vector，也可以用pair。

代码：

class StockSpanner {
public:
    int index=0;
    stackint,int>>s;              //元素类型为pair的栈,键为股票价格,值为日期
    StockSpanner() {
        s.push(make_pair(INT_MAX,0));   //加入哨兵节点（防止操作空栈）
    }   
    
    int next(int price) {
        ++index;
        while(price>=((s.top()).first)){    //保持栈内单调 
            s.pop();
        }
        int res=index-(s.top()).second;     //跨度等于两个下标之差
        s.push(make_pair(price,index));     //存入该节点
        return res;
    }
};