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

每次next会传入一个数字，找出在这个数字之前一共有多少个连续的数字（包括它自己）比它自己小（包括等于）。
注意要是连续的，断了的不算。

思路：

看Example 1, 100前面没有比它小的，只有它自己，所以返回1，同理80, 60,
到70的时候，前面有一个60比它小，包括它自己一共是2个数字，返回2.
后面以此类推。

最直观的方法就是，把所有数字保存到一个数组里面，
后面再来新的数字，就从右到左遍历数组，数数有多少个比新来的数字小。
但是这样每次都需要遍历数组，太耗时。

上面的方法相当于跳过中间所有比它小的数字，等效为，用新来的数字的下标 - 从右到左第一个比它大的数字的下标，
从右到左，后进先出，所以用stack,
保存数字和对应的下标，
每来一个新数字，就把前面比它小（包含等于）的(数字, 下标) pop出来，
然后用新来的下标 - 栈顶元素（第一个比它大的）下标相减。

那如果stack为空了，就相当于用新来的下标 - stack的左边界(-1)

class StockSpanner {
    
    Stack<Pair<Integer, Integer>> st = new Stack<>();
    int idx = -1;

    public StockSpanner() {
        //st = new Stack<>();
    }
    
    public int next(int price) {
        idx ++;
        
        //key:price, value:index
        while(!st.isEmpty() && price >= st.peek().getKey()) {
            st.pop();
        }
        if(st.isEmpty()) {
            st.push(new Pair<Integer, Integer>(price, idx));
            return idx + 1;
        } else {
            int preIdx = st.peek().getValue();
            st.push(new Pair<Integer, Integer>(price, idx));
            
            return (idx - preIdx);
        }
        
        
    }
}
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

用数组模拟stack效率会更高，这里不再用pair，而是分成2个数组

class StockSpanner {
    int N = 10010;
    int[] st = new int[N];
    int[] ids = new int[N];
    int top = -1;
    int index = -1;
    
    public StockSpanner() {
            
    }
    
    public int next(int price) {
        index ++;
        while(top >= 0 && price >= st[top]) {
            top --;
        } 
        
        if(top < 0) {
            top ++;
            st[top] = price;
            ids[top] = index;
            return index + 1;
        }else {
            int preIndex = ids[top];
            top ++;
            st[top] = price;
            ids[top] = index;
            return index - preIndex;
        }
    }
}

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