LeetCode每日一题(901. Online Stock Span)

Design an algorithm that collects daily price quotes for some stock and returns the span of that stock’s price for the current day.

The span of the stock’s price today is defined as the maximum number of consecutive days (starting from today and going backward) for which the stock price was less than or equal to today’s price.

For example, if the price of a stock over the next 7 days were [100,80,60,70,60,75,85], then the stock spans would be [1,1,1,2,1,4,6].
Implement the StockSpanner class:

StockSpanner() Initializes the object of the class.
int next(int price) Returns the span of the stock’s price given that today’s price is price.

Example 1:

Input

[“StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”]
[[], [100], [80], [60], [70], [60], [75], [85]]

Output

[null, 1, 1, 1, 2, 1, 4, 6]

Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today’s price of 75) were less than or equal to today’s price.
stockSpanner.next(85); // return 6

Constraints:

• 1 <= price <= 105
• At most 104 calls will be made to next.

---

用一个 stack 来记录 span，新进来的 price 与前面的 span 的 price 进行对比， 如果 price >= last_span.price, 我们 pop stack 并且 last_span.count 加到当前的 span 中。如果 price < last_span.price, 则把当前 span push 到 stack 中

---

impl StockSpanner {
    fn new() -> Self {
        Self { l: Vec::new() }
    }

    fn next(&mut self, price: i32) -> i32 {
        let mut count = 1;
        while let Some((v, c)) = self.l.pop() {
            if price >= v {
                count += c;
                continue;
            }
            self.l.push((v, c));
            break;
        }
        self.l.push((price, count));
        count
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20