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

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

編寫一個StockSpanner類，它收集某些股票的每日報價，并返回該股票當(dāng)日價格的跨度。
今天股票價格的跨度被定義為股票價格小于或等于今天價格的最大連續(xù)日數(shù)（從今天開始往回數(shù)，包括今天）。
例如，如果未來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) 被調(diào)用并返回 1，
S.next(80) 被調(diào)用并返回 1，
S.next(60) 被調(diào)用并返回 1，
S.next(70) 被調(diào)用并返回 2，
S.next(60) 被調(diào)用并返回 1，
S.next(75) 被調(diào)用并返回 4，
S.next(85) 被調(diào)用并返回 6。

注意 (例如) S.next(75) 返回 4，因為截至今天的最后 4 個價格
(包括今天的價格 75) 小于或等于今天的價格。
提示：

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

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

但是有由于在提示內(nèi)容中已經(jīng)提到了執(zhí)行時間限制的問題，就可以知道這個題目需要進行執(zhí)行時間相關(guān)方面的優(yōu)化。最終我決定使用的優(yōu)化方案是參考跳表這種數(shù)據(jù)結(jié)構(gòu)，利用空間換取時間。思路大致如下，詳細內(nèi)容可以參考實現(xiàn)代碼的第二版：

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

StockSpanner中存儲的是StockPrices的數(shù)組

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

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

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

這個版本是只實現(xiàn)功能的版本，所以提交上去基本都是執(zhí)行超時的結(jié)果。但是可以作為第二版的參考。

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;

    /**
     * 存儲一個遞增數(shù)列的實體
     */
    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){//在當(dāng)前股價區(qū)間內(nèi)
            prices.add(price);
            stockPrices.right=price;
            result+=prices.size();
        }else{//最高位大于當(dāng)前股價，生成一個新的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;
    }
}