901.股票价格跨度

链接：901.股票价格跨度
难度：Medium
标签：栈、设计、数据流、单调栈
简介：编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

题解 1 - python

• 编辑时间：2023-10-07
• 执行用时：356ms
• 内存消耗：20.68MB
• 编程语言：python
• 解法介绍：同上。

class StockSpanner:
    def __init__(self):
        self.idx = 0
        self.arr = []
    def next(self, price: int) -> int:
        while self.arr and self.arr[-1][1] <= price:
            self.arr.pop()
        self.idx += 1
        res = self.idx - (self.arr[-1][0] if self.arr else 0)
        self.arr.append((self.idx, price))
        return res

题解 2 - cpp

• 编辑时间：2023-10-07
• 执行用时：240ms
• 内存消耗：80.53MB
• 编程语言：cpp
• 解法介绍：单调栈。

class StockSpanner {
public:
    int idx;
    vector<pair<int, int>> arr;
    StockSpanner(): idx(0), arr(vector<pair<int, int>>()) {}
    int next(int price) {
        while (arr.size() && arr.back().second <= price) arr.pop_back();
        idx += 1;
        int res = idx - (arr.size() ? arr.back().first : 0);
        arr.push_back(make_pair(idx, price));
        return res;
    }
};

题解 3 - rust

• 编辑时间：2023-10-07
• 执行用时：28ms
• 内存消耗：6.27MB
• 编程语言：rust
• 解法介绍：同上。

struct StockSpanner {
    idx: usize,
    arr: Vec<(usize, i32)>,
}
impl StockSpanner {
    fn new() -> Self {
        Self {
            idx: 0,
            arr: vec![],
        }
    }
    fn next(&mut self, price: i32) -> i32 {
        while !self.arr.is_empty() && self.arr.last().unwrap().1 <= price {
            self.arr.pop();
        }
        self.idx += 1;
        let res = self.idx
            - (if self.arr.is_empty() {
                0
            } else {
                self.arr.last().unwrap().0
            });
        self.arr.push((self.idx, price));
        res as i32
    }
}

题解 4 - typescript

• 编辑时间：2021-07-19
• 执行用时：372ms
• 内存消耗：48.4MB
• 编程语言：typescript
• 解法介绍：单调递减栈，寻找前一个比当前值大的值。

class StockSpanner {
  private arr: number[] = [];
  private stack: number[] = [];
  next(price: number): number {
    const i = this.arr.length;
    this.arr.push(price);
    while (this.stack.length && price >= this.arr[this.stack[this.stack.length - 1]])
      this.stack.pop()!;
    const ans = i - (this.stack[this.stack.length - 1] ?? -1);
    this.stack.push(i);
    return ans;
  }
}

题解 5 - cpp

• 编辑时间：2022-10-21
• 执行用时：196ms
• 内存消耗：84.1MB
• 编程语言：cpp
• 解法介绍：单调栈，存储比自己大的最近节点。

class StockSpanner {
public:
    stack<int> s;
    vector<int> list;
    StockSpanner() {
        list.push_back(0x7fffffff);
        s.push(0);
    }
    int next(int price) {
        while (list[s.top()] <= price) s.pop();
        int res = list.size() - s.top();
        s.push(list.size());
        list.push_back(price);
        return res;
    }
};