05 August 2008
给一个整数数组，返回所有i位置处之前比i位置小或等于的值，包括自己
用单调栈维护一个单调递减的价格序列，并且对于每个价格，存储一个 weight 表示它离上一个价格之间（即最近的一个大于它的价格之间）的天数。如果是栈底的价格，则存储它本身对应的天数。例如 [11, 3, 9, 5, 6, 4, 7] 对应的单调栈为 (11, weight=1), (9, weight=2), (7, weight=4)。
当得到了新的一天的价格，例如 10，将所有栈中所有小于等于 10 的元素全部取出，将它们的 weight 进行累加，再加上 1 就得到了答案。在这之后，我们把 10 和它对应的 weight 放入栈中，得到 (11, weight=1), (10, weight=7)。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class StockSpanner {
Stack<Integer> prices, weights;
public StockSpanner() {
prices = new Stack();
weights = new Stack();
}
public int next(int price) {
int weight = 1;
while (!prices.isEmpty() && prices.peek() <= price) {
prices.pop();
weight += weights.pop();
}
prices.push(price);
weights.push(weight);
return weight;
}
}