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:

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

Source: leetcode | Difficulty: MEDIUM
Tags: Data structures

Starter code: class StockSpanner:
    def __init__(self):
    def next(self, price: int) -> int:
# Your StockSpanner object will be instantiated and called as such:
# obj = StockSpanner()
# param_1 = obj.next(price)

Solutions:
class StockSpanner:

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

	def next(self, price: int) -> int:
		stk = self.s
		curr_span = 1
		while stk and stk[-1][0] <= price:
			(prev_price, prev_span) = stk.pop()
			curr_span += prev_span
		stk.append((price, curr_span))
		return curr_span


class StockSpanner:

	def __init__(self):
		self.s = list()

	def next(self, price: int) -> int:
		weight = 1
		stack = self.s
		while stack and stack[-1][0] <= price:
			weight += stack[-1][-1]
			stack.pop()
		stack.append((price, weight))
		return weight


class StockSpanner:

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

	def next(self, price: int) -> int:
		res = 1
		if not self.stack or price < self.stack[-1]:
			self.stack.append(price)
			self.span.append(1)
		else:
			while self.stack and price >= self.stack[-1]:
				self.stack.pop()
				res += self.span.pop()
			self.stack.append(price)
			self.span.append(res)
		return res


class StockSpanner:

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

	def next(self, price: int) -> int:
		cnt = 1
		while self.st and price >= self.st[-1][0]:
			cnt += self.st.pop()[1]
		self.st.append((price, cnt))
		print(self.st)
		return cnt


class StockSpanner:

	def __init__(self):
		self.stocks = []
		self.spans = []

	def next(self, price: int) -> int:
		self.stocks.append(price)
		self.spans.append(1)
		if len(self.stocks) == 1:
			return self.spans[0]
		idx = len(self.stocks) - 2
		cur_span = self.spans[-1]
		while idx >= 0:
			if price < self.stocks[idx]:
				break
			else:
				cur_span += self.spans[idx]
				idx -= self.spans[idx]
		self.spans[-1] = cur_span
		return self.spans[-1]


class StockSpanner:

	def __init__(self):
		self.stack = list()
		self.ix = -1

	def next(self, price: int) -> int:
		self.ix += 1
		if not self.stack:
			self.stack.append((price, self.ix))
			return 1
		else:
			while self.stack and self.stack[-1][0] <= price:
				self.stack.pop()
			span_start = self.stack[-1][1] if self.stack else -1
			self.stack.append((price, self.ix))
			return self.ix - span_start


class StockSpanner:

	def __init__(self):
		self.history = []
		self.output = []

	def next(self, price: int) -> int:
		less_than_count = 1
		while self.history and self.history[-1][0] <= price:
			less_than_count += self.history.pop()[1]
		self.output.append(less_than_count)
		self.history.append((price, less_than_count))
		return self.output[-1]


class StockSpanner:

	def __init__(self):
		self.stack = [[float('inf'), -1]]
		self.idx = 0

	def next(self, price: int) -> int:
		while self.stack and self.stack[-1][0] <= price:
			self.stack.pop()
		ans = self.idx - self.stack[-1][1]
		self.stack.append([price, self.idx])
		self.idx += 1
		return ans


class StockSpanner:

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

	def next(self, price: int) -> int:
		count = 1
		while self.stack and price >= self.stack[-1][0]:
			count += self.stack[-1][1]
			del self.stack[-1]
		self.stack.append([price, count])
		return self.stack[-1][1]


class StockSpanner:

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

	def next(self, price: int) -> int:
		if not self.q or self.q[-1][0] > price:
			self.q.append((price, 1))
			return 1
		elif self.q and self.q[-1][0] == price:
			(c, l) = self.q.pop()
			self.q.append((price, l + 1))
			return l + 1
		elif self.q:
			level = 1
			while self.q and self.q[-1][0] <= price:
				(c, l) = self.q.pop()
				level += l
			self.q.append((price, level))
			return level


class StockSpanner:

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

	def next(self, price: int) -> int:
		if len(self.spanStk) == 0:
			self.spanStk.append((price, 1))
		else:
			new_weight = 1
			while len(self.spanStk) != 0 and self.spanStk[-1][0] <= price:
				new_weight += self.spanStk[-1][1]
				self.spanStk.pop()
			self.spanStk.append((price, new_weight))
		return self.spanStk[-1][1]


class StockSpanner:

	def __init__(self):
		self.stack = list()
		self.date = 0

	def next(self, price: int) -> int:
		if self.date == 0:
			self.date += 1
			self.stack.append([price, 0])
			return 1
		else:
			(s, e) = (self.date, self.date)
			while len(self.stack) > 0 and self.stack[-1][0] <= price:
				s = self.stack[-1][1]
				self.stack.pop()
			self.stack.append([price, s])
			self.date += 1
			return e - s + 1


class StockSpanner:

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

	def next(self, price: int) -> int:
		if len(self.arr) == 0:
			self.arr.append([price, 1])
			return 1
		i = len(self.arr) - 1
		count = 1
		while i >= 0 and price >= self.arr[i][0]:
			count += self.arr[i][1]
			i -= self.arr[i][1]
		self.arr.append([price, count])
		return count


class StockSpanner:

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

	def next(self, price: int) -> int:
		span = 1
		while self._data and self._data[-1][0] <= price:
			span += self._data.pop()[1]
		self._data.append((price, span))
		return span


class StockSpanner:

	def __init__(self):
		self.cur = -1
		self.stack = []
		self.prices = {}

	def next(self, price: int) -> int:
		self.cur += 1
		self.prices[self.cur] = price
		while self.stack and self.prices[self.stack[-1]] <= price:
			self.prices.pop(self.stack.pop())
		res = self.cur - self.stack[-1] if self.stack else self.cur + 1
		self.stack.append(self.cur)
		return res


class StockSpanner:

	def __init__(self):
		self.stack = [[0, 1]]

	def next(self, price: int) -> int:
		if price < self.stack[-1][0]:
			self.stack.append([price, 1])
			return 1
		else:
			days = 0
			while self.stack and price >= self.stack[-1][0]:
				(p, d) = self.stack.pop()
				days += d
			try:
				days += self.stack[-1][1]
				self.stack[-1][1] = days
			except:
				self.stack.append([0, days])
			self.stack.append([price, 1])
		return days


class StockSpanner:

	def __init__(self):
		self.idx = 0
		self.q = []

	def next(self, price: int) -> int:
		self.idx += 1
		if len(self.q) == 0 or self.q[-1][1] > price:
			self.q.append([self.idx, price])
			return 1
		else:
			while len(self.q) > 0 and self.q[-1][1] <= price:
				self.q.pop()
			if len(self.q) == 0:
				self.q.append([self.idx, price])
				return self.idx
			else:
				self.q.append([self.idx, price])
				return self.idx - self.q[-2][0]


class StockSpanner:

	def __init__(self):
		self.stack = []
		self.pre_less = []
		self.i = 0

	def next(self, price: int) -> int:
		self.i += 1
		while self.stack and self.stack[-1][1] <= price:
			self.stack.pop()
		result = None
		if not self.stack:
			result = self.i
		else:
			result = self.i - self.stack[-1][0]
		self.stack.append((self.i, price))
		return result


class StockSpanner:

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

	def next(self, price: int) -> int:
		self.stack.append([price, 1])
		while len(self.stack) > 1 and self.stack[-1][0] >= self.stack[-2][0]:
			self.stack[-2][0] = self.stack[-1][0]
			self.stack[-2][1] += self.stack[-1][1]
			del self.stack[-1]
		return self.stack[-1][1]


class StockSpanner:

	def __init__(self):
		self.stack = []
		self.ind = 0
		self.vals = []

	def next(self, price):
		self.vals += [price]
		while len(self.stack) > 0 and self.vals[self.stack[-1]] <= price:
			self.stack.pop()
		if len(self.stack) > 0:
			res = self.ind - self.stack[-1]
		else:
			res = self.ind + 1
		self.stack += [self.ind]
		self.ind += 1
		if self.ind == 1:
			return 1
		return res


class StockSpanner:

	def __init__(self):
		self.dp = []
		self.price = []

	def next(self, price: int) -> int:
		if len(self.price) == 0 or price < self.price[-1]:
			self.dp.append(1)
		else:
			i = len(self.price) - 1
			tmp = 1
			while price >= self.price[i] and i >= 0:
				tmp += self.dp[i]
				i -= self.dp[i]
			self.dp.append(tmp)
		self.price.append(price)
		return self.dp[-1]


class StockSpanner:

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

	def next(self, price: int) -> int:
		stack = self.monotone_stack
		(current_price, current_span) = (price, 1)
		while stack and stack[-1][0] <= current_price:
			(pre_price, pre_span) = stack.pop()
			current_span += pre_span
		stack.append((current_price, current_span))
		return current_span


class StockSpanner:

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

	def next(self, price):
		span = 1
		while len(self.st) > 0 and self.st[-1][0] <= price:
			span = span + self.st[-1][1]
			self.st.pop()
		self.st.append((price, span))
		return span


class StockSpanner:

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

	def next(self, price: int) -> int:
		res = 1
		while self.stack and self.stack[-1][0] <= price:
			res += self.stack.pop()[1]
		self.stack.append([price, res])
		return res


class StockSpanner:

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

	def next(self, price):
		while self.stack and self.stack[-1][0] <= price:
			self.stack.pop()
		if self.stack:
			res = self.uid - self.stack[-1][1]
		else:
			res = self.uid
		self.stack.append([price, self.uid])
		self.uid += 1
		return res


from collections import OrderedDict

class StockSpanner(OrderedDict):

	def __init__(self):
		self.counts = 0

	def next(self, price: int) -> int:
		i = len(self) - 1
		idx = self.counts
		items = list(self.items())
		while i >= 0 and items[i][0] <= price:
			idx = self[items[i][0]]
			self.popitem(last=True)
			i -= 1
		self[price] = idx
		self.counts += 1
		return self.counts - idx


class StockSpanner:

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

	def next(self, price: int) -> int:
		while self.stack and self.stack[-1][1] <= price:
			self.stack.pop()
		index = self.stack[-1][0] if self.stack else -1
		diff = self.i - index
		self.stack.append((self.i, price))
		self.i += 1
		return diff


class StockSpanner:

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

	def next(self, price: int) -> int:
		cnt = 1
		while self.stack and self.stack[-1][0] <= price:
			(p, c) = self.stack.pop()
			cnt += c
		self.stack.append([price, cnt])
		return cnt


class StockSpanner:

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

	def next(self, price: int) -> int:
		self.prices.append(price)
		value = 1
		index = len(self.spans) - 1
		while index >= 0:
			if self.prices[index] <= price:
				value += self.spans[index]
				index -= self.spans[index]
			else:
				break
		self.spans.append(value)
		return value


import bisect

class StockSpanner:

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

	def next(self, price: int) -> int:
		total = 1
		while self.stack and self.stack[-1][0] <= price:
			total += self.stack.pop()[1]
		self.stack.append((price, total))
		return total


class StockSpanner:

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

	def next(self, price: int) -> int:
		ans = 1
		while self.st and price >= self.st[-1][0]:
			ans += self.st.pop()[1]
		self.st.append([price, ans])
		return ans


class StockSpanner:

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

	def next(self, price: int) -> int:
		if not self.stock or price < self.stock[-1][0]:
			span = 1
			self.stock.append((price, len(self.stock)))
		else:
			i = self.stock[-1][1] - 1
			while i >= 0 and self.stock[i][0] <= price:
				i -= 1
			span = len(self.stock) - i
			self.stock.append((price, i + 1))
		return span


class StockSpanner:

	def __init__(self):
		self.prices = []
		self.lastP = 0
		self.lastCount = 0

	def next(self, price: int) -> int:
		if len(self.prices) == 0:
			self.lastCount = 1
			self.lastP = 0
			self.prices.append(price)
			return 1
		count = self.lastCount
		if price == self.prices[-1]:
			count += 1
			self.lastCount = count
		elif price > self.prices[-1]:
			count += 1
			isB = False
			for i in range(self.lastP - 1, -1, -1):
				if self.prices[i] <= price:
					count += 1
					self.lastP = i
				else:
					isB = True
					break
			if isB:
				self.lastP = i + 1
			else:
				self.lastP = 0
			self.lastCount = count
		elif price < self.prices[-1]:
			count = 1
			self.lastCount = count
			self.lastP = len(self.prices)
		self.prices.append(price)
		return count


class StockSpanner:

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

	def next(self, price: int) -> int:
		result = 1
		while self.stack and self.stack[-1][0] <= price:
			previous_calculated_result = self.stack.pop()[1]
			result += previous_calculated_result
		self.stack.append([price, result])
		print(self.stack)
		return result


class StockSpanner:

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

	def next(self, price):
		weight = 1
		print(self.stack)
		while self.stack and self.stack[-1][0] <= price:
			weight += self.stack.pop()[1]
		self.stack.append((price, weight))
		return weight


class StockSpanner:

	def __init__(self):
		self.Dict = defaultdict(int)
		self.s = []
		self.count = 0

	def next(self, price: int) -> int:
		if len(self.s) == 0:
			self.s.append((self.count, price))
			self.Dict[self.count, price] += 1
			ans = self.Dict[self.count, price]
			self.count += 1
			return ans
		else:
			while len(self.s) != 0 and price >= self.s[-1][1]:
				self.Dict[self.count, price] += self.Dict[self.s[-1][0], self.s[-1][1]]
				self.s.pop(-1)
			self.s.append((self.count, price))
			self.Dict[self.count, price] += 1
			ans = self.Dict[self.count, price]
			self.count += 1
			return ans


class StockSpanner:

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

	def next(self, price: int) -> int:
		self.prices.append(price)
		length = len(self.prices)
		if length == 1:
			self.counter.append(1)
		elif self.prices[-2] <= price:
			cnt = 0
			for i in range(length - self.counter[-1] - 1, -1, -1):
				if self.prices[i] <= price:
					cnt += 1
				else:
					break
			self.counter.append(self.counter[-1] + cnt)
		else:
			self.counter.append(1)
		return self.counter[-1]


class StockSpanner:

	def __init__(self):
		self.stocks = []
		self.spans = []

	def next(self, price: int) -> int:
		if not self.spans:
			self.spans.append(1)
			self.stocks.append(price)
			return 1
		elif price < self.stocks[-1]:
			self.spans.append(1)
			self.stocks.append(price)
			return 1
		else:
			newSpan = self.spans[-1]
			i = -1 * newSpan - 1
			while i >= -1 * len(self.stocks) and price >= self.stocks[i]:
				newSpan += 1
				i -= 1
			newSpan += 1
			self.spans.append(newSpan)
			self.stocks.append(price)
			return newSpan


class StockSpanner:

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

	def next(self, price: int) -> int:
		stack = self.monotone_stack
		(cur_price_quote, cur_price_span) = (price, 1)
		while stack and stack[-1][0] <= cur_price_quote:
			(prev_price_quote, prev_price_span) = stack.pop()
			cur_price_span += prev_price_span
		stack.append((cur_price_quote, cur_price_span))
		return cur_price_span


class StockSpanner:

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

	def next(self, price: int) -> int:
		res = 1
		i = len(self.stack)
		while self.stack and self.stack[-1][0] <= price:
			(x, c) = self.stack.pop()
			res += c
		self.stack.append((price, res))
		return res


class StockSpanner:

	def __init__(self):
		self.stack = []
		self.num = 0
		self.stack.append((float('inf'), 0))

	def next(self, price: int) -> int:
		ret = 1
		self.num += 1
		while self.stack[-1][0] <= price:
			self.stack.pop()
		topIndex = self.stack[-1][1]
		self.stack.append((price, self.num))
		return self.num - topIndex


class StockSpanner:

	def __init__(self):
		self.priceList = []
		self.n = 0
		self.prevSpan = 0
		self.curSpan = 0

	def next(self, price: int) -> int:
		if not self.priceList:
			self.priceList.append(price)
			self.n += 1
			self.curSpan = 1
			self.prevSpan = self.curSpan
			return self.curSpan
		prev = self.priceList[-1]
		self.priceList.append(price)
		self.n += 1
		if price < prev:
			self.curSpan = 1
			self.prevSpan = self.curSpan
			return self.curSpan
		else:
			self.curSpan = 1 + self.prevSpan
			i = self.n - self.curSpan - 1
			while i >= 0 and self.priceList[i] <= price:
				self.curSpan += 1
				i = self.n - self.curSpan - 1
			self.prevSpan = self.curSpan
			return self.curSpan


from collections import deque

class StockSpanner:

	def __init__(self):
		self.stack = deque()

	def next(self, price: int) -> int:
		weight = 1
		while self.stack and self.stack[-1][0] <= price:
			weight += self.stack.pop()[1]
		self.stack.append((price, weight))
		return weight


class StockSpanner:

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

	def next(self, price: int) -> int:
		if not self.stack:
			self.stack.append((price, 1))
			return 1
		else:
			cnt_removed = 1
			while self.stack and self.stack[-1][0] <= price:
				cnt_removed += self.stack.pop()[1]
			self.stack.append((price, cnt_removed))
			return cnt_removed


class StockSpanner:

	def __init__(self):
		self.nums = []
		self.larger_pos = []

	def next(self, price: int) -> int:
		if not self.nums:
			self.nums.append(price)
			self.larger_pos.append(-1)
			return 1
		num = self.nums[-1]
		pos = len(self.larger_pos) - 1
		while price >= num:
			pos = self.larger_pos[pos]
			if pos == -1:
				self.nums.append(price)
				self.larger_pos.append(-1)
				return len(self.nums)
			num = self.nums[pos]
		self.nums.append(price)
		self.larger_pos.append(pos)
		return len(self.nums) - 1 - pos


class StockSpanner:

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

	def next(self, price: int) -> int:
		val = 1
		while self.stock and self.stock[-1][0] <= price:
			val += self.stock.pop()[1]
		self.stock.append((price, val))
		return val


class StockSpanner:

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

	def next(self, price: int) -> int:
		count = 1
		while self.stack and self.stack[-1][0] <= price:
			(s, c) = self.stack.pop()
			count += c
		self.stack.append((price, count))
		return count


class StockSpanner:

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

	def next(self, price: int) -> int:
		if len(self.stacks) == 0:
			self.stacks.append([price, 1])
			return 1
		else:
			p = 1
			while len(self.stacks) > 0 and self.stacks[-1][0] <= price:
				ele = self.stacks.pop()
				p += ele[1]
			self.stacks.append([price, p])
			return p


class StockSpanner:

	def __init__(self):
		self.stocks = []
		self.topStocks = []

	def next(self, price: int) -> int:
		while len(self.topStocks) > 0 and self.stocks[self.topStocks[-1]] <= price:
			self.topStocks.pop()
		flag = self.topStocks[-1] if len(self.topStocks) > 0 else -1
		self.topStocks.append(len(self.stocks))
		self.stocks.append(price)
		return len(self.stocks) - flag - 1


class StockSpanner:

	def __init__(self):
		self.stack = []
		self.len = -2

	def next(self, price: int) -> int:
		if not self.stack:
			self.stack.append([price, 1])
			return 1
		ans = 0
		while self.stack and self.stack[-1][0] <= price:
			elm = self.stack.pop()
			ans += elm[1]
		self.stack.append([price, ans + 1])
		return ans + 1


from collections import deque

class StockSpanner:

	def __init__(self):
		self.stack = deque()
		self.counter = 0
		self.stack.append([float('inf'), 0])

	def update_stack(self, value):
		while value >= self.stack[len(self.stack) - 1][0]:
			self.stack.pop()

	def next(self, price: int) -> int:
		self.counter += 1
		self.update_stack(price)
		diff = abs(self.counter - self.stack[len(self.stack) - 1][1])
		self.stack.append([price, self.counter])
		return diff


class StockSpanner:

	def __init__(self):
		self.st = []
		self.idx = 0

	def next(self, price: int) -> int:
		while len(self.st) and self.st[-1][0] <= price:
			self.st.pop()
		ans = self.idx - (0 if not len(self.st) else self.st[-1][1]) + 1
		self.st.append((price, self.idx + 1))
		self.idx += 1
		return ans


class StockSpanner:

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

	def next(self, price: int) -> int:
		cur = len(self.prices) - 1
		while cur >= 0 and self.prices[cur] <= price:
			cur = self.left[cur]
		self.left.append(cur)
		self.prices.append(price)
		return len(self.prices) - 1 - cur


class StockSpanner:

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

	def next(self, price: int) -> int:
		while self.decreasing_stack and self.prices[self.decreasing_stack[-1]] <= price:
			self.decreasing_stack.pop()
		ret = len(self.prices) - self.decreasing_stack[-1] if self.decreasing_stack else len(self.prices) + 1
		self.decreasing_stack.append(len(self.prices))
		self.prices.append(price)
		return ret


class StockSpanner:

	def __init__(self):
		self.s = []
		self.O = []

	def next(self, price: int) -> int:
		self.s.append(price)
		o = 0
		if len(self.s) == 1:
			self.O.append(1)
			return 1
		l = len(self.s)
		i = l - 2
		o = 1
		while i >= 0:
			if self.s[i] <= price:
				o += self.O[i]
				i -= self.O[i]
			else:
				break
		self.O.append(o)
		return o


class StockSpanner:

	def __init__(self):
		self.stack = []
		self.indx = -1
		self.results = []

	def next(self, price: int) -> int:
		self.indx += 1
		while len(self.stack) > 0 and self.stack[-1][1] <= price:
			self.stack.pop()
		if len(self.stack) == 0:
			self.stack.append([self.indx, price])
			return self.indx + 1
		result = self.stack[-1][0]
		self.stack.append([self.indx, price])
		return self.indx - result


class StockSpanner:

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

	def next(self, price: int) -> int:
		weight = 1
		while self.stack and self.stack[-1][0] <= price:
			(_, currentWeight) = self.stack.pop()
			weight += currentWeight
		self.stack.append((price, weight))
		return weight


class StockSpanner:

	def __init__(self):
		self.s = [float('inf')]
		self.pos = [0]
		self.num = 1

	def next(self, price: int) -> int:
		while self.s and self.s[-1] <= price:
			self.s.pop()
			self.pos.pop()
		r = self.num - self.pos[-1]
		self.s.append(price)
		self.pos.append(self.num)
		self.num += 1
		return r