设计一个算法收集某些股票的每日报价，并返回该股票当日价格的 跨度 。
当日股票价格的 跨度 被定义为股票价格小于或等于今天价格的最大连续日数（从今天开始往回数，包括今天）。
- 例如，如果未来 7 天股票的价格是
[100,80,60,70,60,75,85]，那么股票跨度将是 [1,1,1,2,1,4,6] 。
实现 StockSpanner 类：
StockSpanner() 初始化类对象。int next(int price) 给出今天的股价 price ，返回该股票当日价格的 跨度 。
示例：
**输入** ：
["StockSpanner", "next", "next", "next", "next", "next", "next", "next"]
[[], [100], [80], [60], [70], [60], [75], [85]]
**输出** ：
[null, 1, 1, 1, 2, 1, 4, 6]
**解释：**
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // 返回 1
stockSpanner.next(80); // 返回 1
stockSpanner.next(60); // 返回 1
stockSpanner.next(70); // 返回 2
stockSpanner.next(60); // 返回 1
stockSpanner.next(75); // 返回 4 ，因为截至今天的最后 4 个股价 (包括今天的股价 75) 都小于或等于今天的股价。
stockSpanner.next(85); // 返回 6
提示：
1 <= price <= 105- 最多调用
next 方法 104 次
方法一：单调栈
思路
调用 next 时，输入是新的一天的股票价格，需要返回包含此日在内的，往前数最多有连续多少日的股票价格是小于等于今日股票价格的。如果把每日的 price 当成数组不同下标的值，即需要求出每个值与上一个更大元素之间的下标之差。这种题目可以用单调栈求解，具体原理可以参考「496. 下一个更大元素 I 的官方题解的方法二 」。此题的具体解法上，栈的元素可以是股票价格的下标（即天数）和股票价格的二元数对，并且在栈中先插入一个最大值作为天数为 -1 天的价格，来保证栈不会为空。调用 next 时，先将栈中价格小于等于此时 price 的元素都弹出，直到遇到一个大于 price 的值，并将 price 入栈，计算下标差返回。
代码
[sol1-Python3]1
2
3
4
5
6
7
8
9
10
11
| class StockSpanner:
def __init__(self):
self.stack = [(-1, inf)]
self.idx = -1
def next(self, price: int) -> int:
self.idx += 1
while price >= self.stack[-1][1]:
self.stack.pop()
self.stack.append((self.idx, price))
return self.idx - self.stack[-2][0]
|
[sol1-Java]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class StockSpanner {
Deque<int[]> stack;
int idx;
public StockSpanner() {
stack = new ArrayDeque<int[]>();
stack.push(new int[]{-1, Integer.MAX_VALUE});
idx = -1;
}
public int next(int price) {
idx++;
while (price >= stack.peek()[1]) {
stack.pop();
}
int ret = idx - stack.peek()[0];
stack.push(new int[]{idx, price});
return ret;
}
}
|
[sol1-C#]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| public class StockSpanner {
Stack<Tuple<int, int>> stack;
int idx;
public StockSpanner() {
stack = new Stack<Tuple<int, int>>();
stack.Push(new Tuple<int, int>(-1, int.MaxValue));
idx = -1;
}
public int Next(int price) {
idx++;
while (price >= stack.Peek().Item2) {
stack.Pop();
}
int ret = idx - stack.Peek().Item1;
stack.Push(new Tuple<int, int>(idx, price));
return ret;
}
}
|
[sol1-C++]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| class StockSpanner {
public:
StockSpanner() {
this->stk.emplace(-1, INT_MAX);
this->idx = -1;
}
int next(int price) {
idx++;
while (price >= stk.top().second) {
stk.pop();
}
int ret = idx - stk.top().first;
stk.emplace(idx, price);
return ret;
}
private:
stack<pair<int, int>> stk;
int idx;
};
|
[sol1-C]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| typedef struct Node {
int first;
int second;
struct Node *next;
} Node;
typedef struct {
Node *stack;
int idx;
} StockSpanner;
Node* nodeCreate(int first, int second) {
Node *obj = (Node *)malloc(sizeof(Node));
obj->first = first;
obj->second = second;
obj->next = NULL;
return obj;
}
StockSpanner* stockSpannerCreate() {
StockSpanner *obj = (StockSpanner *)malloc(sizeof(StockSpanner));
obj->idx = -1;
obj->stack = nodeCreate(-1, INT_MAX);
return obj;
}
int stockSpannerNext(StockSpanner* obj, int price) {
obj->idx++;
while (price >= obj->stack->second) {
Node *p = obj->stack;
obj->stack = obj->stack->next;
free(p);
}
int ret = obj->idx - obj->stack->first;
Node *p = nodeCreate(obj->idx, price);
p->next = obj->stack;
obj->stack = p;
return ret;
}
void stockSpannerFree(StockSpanner* obj) {
for (Node *p = obj->stack; p;) {
Node *node = p;
p = p->next;
free(node);
}
free(obj);
}
|
[sol1-JavaScript]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
| var StockSpanner = function() {
this.stack = [];
this.stack.push([-1, Number.MAX_VALUE]);
this.idx = -1;
};
StockSpanner.prototype.next = function(price) {
this.idx++;
while (price >= this.stack[this.stack.length - 1][1]) {
this.stack.pop();
}
let ret = this.idx - this.stack[this.stack.length - 1][0];
this.stack.push([this.idx, price]);
return ret;
};
|
[sol1-Golang]1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| type StockSpanner struct {
stack [][2]int
idx int
}
func Constructor() StockSpanner {
return StockSpanner{[][2]int{{-1, math.MaxInt32}}, -1}
}
func (s *StockSpanner) Next(price int) int {
s.idx++
for price >= s.stack[len(s.stack)-1][1] {
s.stack = s.stack[:len(s.stack)-1]
}
s.stack = append(s.stack, [2]int{s.idx, price})
return s.idx - s.stack[len(s.stack)-2][0]
}
|
复杂度分析
