[Swift]LeetCode901. 股票价格跨度 | Online Stock Span

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

➤微信公众号：山青咏芝（shanqingyongzhi）

➤博客园地址：山青咏芝（https://www.cnblogs.com/strengthen/）

➤GitHub地址：https://github.com/strengthen/LeetCode

➤原文地址： https://www.cnblogs.com/strengthen/p/10607919.html 

➤如果链接不是山青咏芝的博客园地址，则可能是爬取作者的文章。

➤原文已修改更新！强烈建议点击原文地址阅读！支持作者！支持原创！

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

Write a class StockSpanner which 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 backwards) for which the price of the stock 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]. 

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: 
First, S = StockSpanner() is initialized.  Then:
S.next(100) is called and returns 1,
S.next(80) is called and returns 1,
S.next(60) is called and returns 1,
S.next(70) is called and returns 2,
S.next(60) is called and returns 1,
S.next(75) is called and returns 4,
S.next(85) is called and returns 6.Note that (for example) S.next(75) returned 4, because the last 4 prices
(including today's price of 75) were less than or equal to today's price. 

Note:

1. Calls to StockSpanner.next(int price) will have 1 <= price <= 10^5.
2. There will be at most 10000 calls to StockSpanner.next per test case.
3. There will be at most 150000 calls to StockSpanner.next across all test cases.
4. The total time limit for this problem has been reduced by 75% for C++, and 50% for all other languages.

---

编写一个 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) 小于或等于今天的价格。 

提示：

1. 调用 StockSpanner.next(int price) 时，将有 1 <= price <= 10^5。
2. 每个测试用例最多可以调用  10000 次 StockSpanner.next。
3. 在所有测试用例中，最多调用 150000 次 StockSpanner.next。
4. 此问题的总时间限制减少了 50%。

---

Runtime: 840 ms

Memory Usage: 23 MB

class StockSpanner {
    var spans:[Int]
    var prices:[Int]
    var index:Int

    init() {
        spans = [Int](repeating:0,count:10_000)
        prices = [Int](repeating:0,count:10000)
        index = -1
    }
    
    func next(_ price: Int) -> Int {
        index += 1
        prices[index] = price
        if index == 0 || price < prices[index - 1]
        {
            spans[index] = 1
            return 1
        }
        var previousIndex:Int = index - 1
        var span:Int = 1
        while (previousIndex >= 0 && price >= prices[previousIndex])
        {
            span += spans[previousIndex]
            previousIndex -= spans[previousIndex]
        }
        spans[index] = span
        return span
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * let obj = StockSpanner()
 * let ret_1: Int = obj.next(price)
 */

---

892ms

class StockSpanner {

    private var s = [(Int, Int)]()
    init() {
        
    }
    
    func next(_ price: Int) -> Int {
        var sum = 1
        while !s.isEmpty, s.last!.0 <= price {
            sum += s.removeLast().1
        }
        s.append((price, sum))
        return sum
    }
}

---

928ms

class StockSpanner {

    init() {
        
    }
    
    struct PriceSpan {
        let price: Int
        let span: Int
    }
    
    var stack = [PriceSpan]()
    
    func next(_ price: Int) -> Int {
        guard stack.count > 0 else {
            stack.append(PriceSpan(price: price, span: 1))
            return 1
        }
        
        var span = 1
        while stack.last != nil && stack.last!.price <= price {
            span += stack.last!.span
            stack.removeLast()
        }
        
        stack.append(PriceSpan(price: price, span: span))
        return span
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * let obj = StockSpanner()
 * let ret_1: Int = obj.next(price)
 */

---

1036ms

class StockSpanner {
    private var span: [Int] = []
    private var stack: [StockSpan] = []
    init() {
        
    }
    
    func next(_ price: Int) -> Int {
        var stockSpan = StockSpan(price:price, span: 1)
        while !stack.isEmpty && stack.last!.price <= stockSpan.price {
            let removed = stack.removeLast()
            stockSpan.span += removed.span
        }
        stack.append(stockSpan)
        return stockSpan.span
    }
    
    struct StockSpan {
        let price: Int 
        var span: Int
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * let obj = StockSpanner()
 * let ret_1: Int = obj.next(price)
 */ 

---

20764 kb

class StockSpanner {
    var prices: [Int] = []
    var days: [Int] = []
    init() {
        
    }
    
    func next(_ price: Int) -> Int {
        if prices.isEmpty || prices.last! > price {
            prices.append(price)
            days.append(1)
            return 1
        }
        var index = prices.count - 1
        var res = 1
        while index >= 0 && prices[index] <= price {
            res += days[index]
            index -= days[index]
        }
        prices.append(price)
        days.append(res)
        return res
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * let obj = StockSpanner()
 * let ret_1: Int = obj.next(price)
 */

---

20820 kb

class StockSpanner {
    
    private var elements : [(price : Int, conquered : Int)] = []
    init() {
        
    }
    
    func next(_ price: Int) -> Int {
        var conquered : Int = 1
        while !elements.isEmpty && elements.last!.price <= price {
            let removed = elements.removeLast()
            conquered += removed.conquered
        }
        
        elements.append((price: price, conquered: conquered))
        return elements.last!.conquered
    }
}

/**
 * Your StockSpanner object will be instantiated and called as such:
 * let obj = StockSpanner()
 * let ret_1: Int = obj.next(price)
 */