- 2020-07-27 06:44
*views 24*- leetcode
- c language
- Python
- lintcode
- Stack

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

- Python153 blogs
- Java137 blogs
- Vue88 blogs
- Flow Chart79 blogs
- javascript44 blogs
- C++43 blogs
- MySQL39 blogs
- programing language39 blogs
- more...

Daily Recommendation

©2020-2021 ioDraw All rights reserved

MySQL— Relational database element-ui in collapse Default deployment heap （ Big root pile , Small root pile ） Ali four sides ： You know? Spring AOP establish Proxy The process ?HTML+CSS+JS Realized games -" scissors "【139】 Alicloud cloud disk mounting method sql Grouping statistics _SQL— Summary analysis SQL Different values for the same field in , Conduct data statistics Android 11 Official release !python Read from the specified directory Excel Table all sheet Data