Write one StockSpanner class , It collects daily quotes for certain stocks , And returns the span of the current price of the stock .
The span of today's stock price is defined as the maximum number of consecutive days when the stock price is less than or equal to today's price （ Count back from today , Including today ）.
for example , If the future 7 What's the price of the stock [100, 80, 60, 70, 60, 75, 85], So the stock span will be [1, 1, 1, 2, 1, 4, 6].
* call StockSpanner.next(int price) Time , There will be 1 <= price <= 10^5.
* Each test case can be called at most 10000 second StockSpanner.next.
* In all test cases , Call at most 150000 second StockSpanner.next.
* The total time limit for this problem is reduced 50%.
Examples 1:
input ：prices = [100,80,60,70,60,75,85] output ：[1,1,1,2,1,4,6] explain ： first , initialization S =
StockSpanner(), then ： S.next(100) Called and returned 1, S.next(80) Called and returned 1, S.next(60) Called and returned
1, S.next(70) Called and returned 2, S.next(60) Called and returned 1, S.next(75) Called and returned 4, S.next(85)
Called and returned 6. be careful ( for example ) S.next(75) return 4, Because by the end of the day 4 Price ( Including today's price 75) Less than or equal to today's price .
Examples 2:
input ：prices = [50,80,80,70,90,75,85] output ：[1,2,3,1,5,1,2] explain ： first , initialization S =
StockSpanner(), then ： S.next(50) Called and returned 1, S.next(80) Called and returned 2, S.next(80) Called and returned
3, S.next(70) Called and returned 1, S.next(90) Called and returned 5, S.next(75) Called and returned 1, S.next(85)
Called and returned 2.
【 Explanation 】
Monotone stack problem The maximum number of consecutive days when the stock price is less than or equal to today's price .
Because this is an online problem , So we must input price Put it in storage , And at the same time, we need to keep the information that we entered for the first time .
What needs attention is the boundary problem , When we enter the first one price When , here stack empty . So take it out here to judge the special treatment .
public class StockSpanner { public StockSpanner() { } /** * @param price: *
@return: int */ Stack<int[]> stack = new Stack<>(); public int next(int price)
{ // Write your code here. int res = 1; while (!stack.isEmpty() &&
stack.peek()[0] <= price) res += stack.pop()[1]; stack.push(new int[]{price,
res}); return res; } }
Technology
Daily Recommendation