摘要：前言的第二道題目，同樣是分值分且中等難度的題目股票價格跨度編寫一個類，它收集某些股票的每日報價，并返回該股票當日價格的跨度。第二版股票價格跨度存儲一個遞增數列的實體最低位最高位在當前股價區間內最高位大于當前股價，生成一個新的

Weekly Contest 101的第二道題目，同樣是分值4分且中等難度的題目股票價格跨度：

編寫一個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) 小于或等于今天的價格。
提示：

調用StockSpanner.next(int price) 時，將有1 <= price <= 10^5。
每個測試用例最多可以調用10000次StockSpanner.next。
在所有測試用例中，最多調用150000次StockSpanner.next。
此問題的總時間限制減少了50%。

這道題目其實如果只是實現題目的功能要求的話是一道很簡單的題目。只是不斷獲取一個數組從最后一個元素開始單調遞增數列的長度。

但是有由于在提示內容中已經提到了執行時間限制的問題，就可以知道這個題目需要進行執行時間相關方面的優化。最終我決定使用的優化方案是參考跳表這種數據結構，利用空間換取時間。思路大致如下，詳細內容可以參考實現代碼的第二版：

定義一個存儲遞增數列的實體StockPrices，該實體還會記錄最高位(第一個元素)和最低位(最后一個元素)

StockSpanner中存儲的是StockPrices的數組

每當有新股價進入，逆序(從最后一個元素開始)遍歷StockSpanner的StockPrices數組。然后根據是否在當前的遞增數列的范圍進行處理。

以示例作為例子：
初始化后

pricesList:[
    {
        left:0
        right:0
        prices:[]
    }

next(100)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    }
return 1

next(80)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    }]
return 1

next(60)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    }
    {
        left:60
        right:60
        prices:[60]
    }]
    
return 1  

next(70)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    }]
    
return 2 

next(60)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    },
    {
        left:60
        right:60
        prices:[60]
    }]
   
return 1 

next(75)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    },
    {
        left:60
        right:75
        prices:[60,75]
    }]
   
return 4 

next(85)

pricesList:[
    {
        left:100
        right:100
        prices:[100]
    },
    {
        left:80
        right:80
        prices:[80]
    },
    {
        left:60
        right:70
        prices:[60,70]
    },
    {
        left:60
        right:85
        prices:[60,75,85]
    }]
   
return 6

這個版本是只實現功能的版本，所以提交上去基本都是執行超時的結果。但是可以作為第二版的參考。

class StockSpanner {

    private List prices;

    public StockSpanner() {
        prices=new ArrayList();
    }

    public int next(int price) {
        int result=1;
        prices.add(price);
        int days=prices.size();
        if(days>1){
            int todayPrice=price;
            for(int i=days-2;i>=0;i--){
                if(todayPrice>=prices.get(i)){
                    ++result;
                }else{
                    break;
                }
            }
        }
        return result;
    }
}

/**
 * 股票價格跨度
 * @author RJH
 * create at 2018/9/9
 */
public class StockSpanner {

    private List pricesList;

    /**
     * 存儲一個遞增數列的實體
     */
    class StockPrices{
        /**
         * 最低位
         */
        int left;
        /**
         * 最高位
         */
        int right;
        /**
         *
         */
        List prices=new ArrayList<>();
    }


    public StockSpanner() {
        pricesList=new ArrayList<>();
        StockPrices stockPrices=new StockPrices();
        pricesList.add(stockPrices);
    }

    public int next(int price) {
        int result=0;
        StockPrices stockPrices=pricesList.get(pricesList.size()-1);
        List prices=stockPrices.prices;
        if(prices.size()==0){
            stockPrices.left=price;
            stockPrices.right=price;
            prices.add(price);
            result+=prices.size();
            return result;
        }
        if(stockPrices.right<=price){//在當前股價區間內
            prices.add(price);
            stockPrices.right=price;
            result+=prices.size();
        }else{//最高位大于當前股價，生成一個新的StockPrices
            StockPrices newStockPrices=new StockPrices();
            newStockPrices.prices=new ArrayList<>();
            newStockPrices.prices.add(price);
            newStockPrices.left=price;
            newStockPrices.right=price;
            result+=newStockPrices.prices.size();
            pricesList.add(newStockPrices);
        }
        for(int i=pricesList.size()-2;i>=0;i--){
            StockPrices sp=pricesList.get(i);
            if(sp.right>price){
                break;
            }else if(sp.left>price){
                for(int j=sp.prices.size()-1;j>=0;j--){
                    if(price<=sp.prices.get(j)){
                        ++result;
                    }
                }
            }else if(sp.left<=price){
                result+=sp.prices.size();
            }
        }
        return result;
    }
}