901.股票价格跨度

【LetMeFly】901.股票价格跨度

力扣题目链接：https://leetcode.cn/problems/online-stock-span/

编写一个 StockSpanner 类，它收集某些股票的每日报价，并返回该股票当日价格的跨度。

今天股票价格的跨度被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。

例如，如果未来7天股票的价格是 [100, 80, 60, 70, 60, 75, 85]，那么股票跨度将是 [1, 1, 1, 2, 1, 4, 6]。

 

示例：

输入：["StockSpanner","next","next","next","next","next","next","next"], [[],[100],[80],[60],[70],[60],[75],[85]]
输出：[null,1,1,1,2,1,4,6]
解释：
首先，初始化 S = StockSpanner()，然后：
S.next(100) 被调用并返回 1，
S.next(80) 被调用并返回 1，
S.next(60) 被调用并返回 1，
S.next(70) 被调用并返回 2，
S.next(60) 被调用并返回 1，
S.next(75) 被调用并返回 4，
S.next(85) 被调用并返回 6。

注意 (例如) S.next(75) 返回 4，因为截至今天的最后 4 个价格
(包括今天的价格 75) 小于或等于今天的价格。

 

提示：

1. 调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
2. 每个测试用例最多可以调用  10000 次 StockSpanner.next。
3. 在所有测试用例中，最多调用 150000 次 StockSpanner.next。
4. 此问题的总时间限制减少了 50%。

方法一：单调栈

建立一个单调栈，其中数据类型<价格, 连续天数>

当新元素价格大于栈顶价格时，不断出栈并累加连续天数，最终天数即为答案。

初始值是一个“无穷大的价格”

以样例一[100, 80, 60, 70, 60, 75, 85]为例：

[ (2147483647, 6666666)
              这个数随意

第一个数100：

构造(100, 1)

100小于栈顶元素2147483647

(100, 1)入栈，并返回1

[ (2147483647, 6666666), (100, 1)

第二个数80：

构造(80, 1)

80小于栈顶元素100

(80, 1)入栈，并返回1

[ (2147483647, 6666666), (100, 1), (80, 1)

第三个数60：

构造(60, 1)

60小于栈顶元素80

(60, 1)入栈，并返回1

[ (2147483647, 6666666), (100, 1), (80, 1), (60, 1)

第四个数70：

构造(70, 1)

70大于栈顶元素60

(60, 1)出栈，(70, 1)的连续天数加上(60, 1)的1变成(70, 2)

[ (2147483647, 6666666), (100, 1), (80, 1)

继续和栈顶元素比较

70小于栈顶元素80

(70, 2)入栈，并返回2

[ (2147483647, 6666666), (100, 1), (80, 1), (70, 2)

第五个数60：

构造(60, 1)

60小于栈顶元素70

(60, 1)入栈，并返回1

[ (2147483647, 6666666), (100, 1), (80, 1), (70, 2), (60, 1)

第六个数75：

构造(75, 1)

75大于栈顶元素60

(60, 1)出栈，(75, 1)的连续天数加上(60, 1)的1变成(75, 2)

[ (2147483647, 6666666), (100, 1), (80, 1), (70, 2)

继续和栈顶元素比较

75大于栈顶元素70

(70, 2)出栈，(75, 2)的连续天数加上(70, 2)的2变成(75, 4)

[ (2147483647, 6666666), (100, 1), (80, 1)

继续和栈顶元素比较

75小于栈顶元素80

(75, 4)入栈，并返回4

[ (2147483647, 6666666), (100, 1), (80, 1), (75, 4)

第七个数85：

构造(85, 1)

85大于栈顶元素75

(75, 4)出栈，(85, 1)的连续天数加上(75, 4)的4变成(85, 5)

[ (2147483647, 6666666), (100, 1), (80, 1)

继续和栈顶元素比较

85大于栈顶元素80

(80, 1)出栈，(85, 5)的连续天数加上(80, 1)的1变成(85, 6)

[ (2147483647, 6666666), (100, 1)

继续和栈顶元素比较

85小于栈顶元素1000

(85, 6)入栈，并返回6

[ (2147483647, 6666666), (100, 1), (85, 6)

任务完成。

• 时间复杂度$O(N)$，其中一共调用了$N$次next()函数，平均单次时间复杂度$O(1)$
• 空间复杂度$O(N)$

AC代码

C++

typedef pair<int, int> pii;  // <price, 连续>
class StockSpanner {
private:
    stack<pii> st;
public:
    StockSpanner() {
        st.push({INT_MAX, 666});
    }
    
    int next(int price) {
        int cnt = 1;
        while (price >= st.top().first) {
            cnt += st.top().second;
            st.pop();
        }
        st.push({price, cnt});
        return cnt;
    }
};

Python

class StockSpanner:

    def __init__(self):
        self.st = []  # <price, cnt>


    def next(self, price: int) -> int:
        ans = 1
        while len(self.st) and self.st[-1][0] <= price:
            ans += self.st[-1][1]
            self.st.pop()
        self.st.append([price, ans])
        return ans

同步发文于CSDN，原创不易，转载请附上原文链接哦~
Tisfy：https://letmefly.blog.csdn.net/article/details/127453430