当前位置：首页 > article >正文

leetcode 901. 股票价格跨度

article 2025/2/5 17:42:11

题目如下
在这里插入图片描述
数据范围

示例

本题意思就是从当前数开始向前数有几个连续小于或等于自己的数。
观察到next最多被调用10000次，那么理论上使用n方复杂度的算法暴力枚举也是可以的。
但是这样的重复计算太多如果操作不当还是很容易超时的。就拿示例一来说85>75暴力法还是要比较75前60 70 60所以如何减少重复计算呢？
显然我们要找小于等于自己数的数量那反过来不就是寻找左边第一个大于自己的数吗？
所以这里我们可以借助单调栈仅通过一次遍历来快速寻找左边第一个大于自己的。

通过代码

class dat {
public:
    dat(int a,int b) {
        d = a;
        i = b;//记录索引
    }
    int d;
    int i;

};
class StockSpanner {
public:
    stack<dat> stack;
    int count = 0;
    StockSpanner() {
        stack.emplace(1000000,-1);
    }

    int next(int price) {
      while(stack.top().d <= price) {
          stack.pop();
      }
      int i = stack.top().i;  
      stack.emplace(price,count++);
      return count - 1 - i; 
    }
};
/**
 * Your StockSpanner object will be instantiated and called as such:
 * StockSpanner* obj = new StockSpanner();
 * int param_1 = obj->next(price);
 */