leetcode 901 股票价格跨度

首先我用插入排序的思想，直接爆破，然后超时没找出来。

class StockSpanner(object):

    def __init__(self):
        self.prices = []

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        self.prices.append(price)

        j = len(self.prices) - 1
        while j >= 0 and self.prices[j] <= price:
            j -= 1
        return len(self.prices) - j - 1
       

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

后来想了想，用个栈就能解决，里面放二维数组。保存最大的价格和最大的天数。

class StockSpanner(object):

    def __init__(self):
        self.stack = []

    def next(self, price):
        """
        :type price: int
        :rtype: int
        """
        days = 1
        
        while self.stack and price >= self.stack[-1][0]:
            t = self.stack.pop()
            days += t[1]
        self.stack.append([price, days])
        return self.stack[-1][1]

# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

手写代码时，操作步骤是先写几个测试用例出来，然后在想思路，最后编码实现。。。

做人真的好难！！！