diff options
-rw-r--r-- | online_stock_span.c | 85 | ||||
-rw-r--r-- | online_stock_span.cpp | 20 | ||||
-rw-r--r-- | online_stock_span.py | 33 | ||||
-rw-r--r-- | online_stock_span.rs | 33 |
4 files changed, 162 insertions, 9 deletions
diff --git a/online_stock_span.c b/online_stock_span.c new file mode 100644 index 0000000..bfa3895 --- /dev/null +++ b/online_stock_span.c @@ -0,0 +1,85 @@ +// 901. Online Stock Span +#include "leetcode.h" + +/* + * design an algorithm that 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 in one day is the maximum number of consecutive days (starting + * from that day and going backward) for which the stock price was less than or + * equal to the price of that day. if the prices of the stock in the last four + * days is '[7,34,1,2]' and the price of the stock today is 8, then the span of + * today is 3 because starting from today, the price of the stock was less than + * or equal 8 for 3 consecutive days. + */ + +typedef struct { + int first; + int second; +} pair; + +typedef struct { + pair data; + struct node *next; +} node; + +typedef struct { + node *top; +} StockSpanner; + +node *create_node(pair data) { + node *new = (node *)malloc(sizeof(node)); + new->data = data; + new->next = NULL; + return new; +} + +StockSpanner *stockSpannerCreate() { + StockSpanner *obj = (StockSpanner *)malloc(sizeof(StockSpanner)); + obj->top = NULL; + return obj; +} + +void push(StockSpanner *obj, pair data) { + node *curr = create_node(data); + curr->next = obj->top; + obj->top = curr; +} + +pair pop(StockSpanner *obj) { + if (obj->top == NULL) { + pair empty = {0, 0}; + return empty; + } + node *tmp = obj->top; + pair data = tmp->data; + obj->top = tmp->next; + free(tmp); + return data; +} + +int stockSpannerNext(StockSpanner *obj, int price) { + int cnt = 1; + while (obj->top && obj->top->data.first <= price) { + cnt += obj->top->data.second; + pop(obj); + } + push(obj, (pair){price, cnt}); + return cnt; +} + +void stockSpannerFree(StockSpanner *obj) { + while (obj->top) + pop(obj); + free(obj); +} + +int main() { + StockSpanner *obj = stockSpannerCreate(); + printf("%d\n", stockSpannerNext(obj, 100)); // expect: 1 + printf("%d\n", stockSpannerNext(obj, 80)); // expect: 1 + printf("%d\n", stockSpannerNext(obj, 60)); // expect: 1 + printf("%d\n", stockSpannerNext(obj, 70)); // expect: 2 + printf("%d\n", stockSpannerNext(obj, 60)); // expect: 1 + printf("%d\n", stockSpannerNext(obj, 75)); // expect: 4 + printf("%d\n", stockSpannerNext(obj, 85)); // expect: 6 +} diff --git a/online_stock_span.cpp b/online_stock_span.cpp index 6d56038..340f32e 100644 --- a/online_stock_span.cpp +++ b/online_stock_span.cpp @@ -1,5 +1,17 @@ +// 901. Online Stock Span #include "leetcode.h" +/* + * design an algorithm that 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 in one day is the maximum number of consecutive days (starting + * from that day and going backward) for which the stock price was less than or + * equal to the price of that day. if the prices of the stock in the last four + * days is '[7,34,1,2]' and the price of the stock today is 8, then the span of + * today is 3 because starting from today, the price of the stock was less than + * or equal 8 for 3 consecutive days. + */ + class StockSpanner { public: stack<pair<int, int>> storage; @@ -21,5 +33,11 @@ public: int main() { StockSpanner *obj = new StockSpanner(); - int param_1 = obj->next(price); + printf("%d\n", obj->next(100)); // expect: 1 + printf("%d\n", obj->next(80)); // expect: 1 + printf("%d\n", obj->next(60)); // expect: 1 + printf("%d\n", obj->next(70)); // expect: 2 + printf("%d\n", obj->next(60)); // expect: 1 + printf("%d\n", obj->next(75)); // expect: 4 + printf("%d\n", obj->next(85)); // expect: 6 } diff --git a/online_stock_span.py b/online_stock_span.py new file mode 100644 index 0000000..9cd8c3a --- /dev/null +++ b/online_stock_span.py @@ -0,0 +1,33 @@ +# 901. Online Stock Span + +""" +design an algorithm that collects daily price quotes for some stock and +from that day and going backward) for which the stock price was less than or +equal to the price of that day. if the prices of the stock in the last four +days is '[7,34,1,2]' and the price of the stock today is 8, then the span of +today is 3 because starting from today, the price of the stock was less than +or equal 8 for 3 consecutive days. +""" + + +class StockSpanner: + def __init__(self): + self.stack = [] + + def next(self, price: int) -> int: + ans = 1 + while self.stack and self.stack[-1][0] <= price: + ans += self.stack.pop()[1] + self.stack.append([price, ans]) + return ans + + +if __name__ == "__main__": + obj = StockSpanner() + print(obj.next(100)) + print(obj.next(80)) + print(obj.next(60)) + print(obj.next(70)) + print(obj.next(60)) + print(obj.next(75)) + print(obj.next(85)) diff --git a/online_stock_span.rs b/online_stock_span.rs index a1818ff..a967028 100644 --- a/online_stock_span.rs +++ b/online_stock_span.rs @@ -1,17 +1,28 @@ +// 901. Online Stock Span + +/* + * design an algorithm that 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 in one day is the maximum number of consecutive days (starting + * from that day and going backward) for which the stock price was less than or + * equal to the price of that day. if the prices of the stock in the last four + * days is '[7,34,1,2]' and the price of the stock today is 8, then the span of + * today is 3 because starting from today, the price of the stock was less than + * or equal 8 for 3 consecutive days. + */ + struct Span { price: i32, - days: i32 + days: i32, } struct StockSpanner { - spans: Vec<Span> + spans: Vec<Span>, } impl StockSpanner { fn new() -> Self { - StockSpanner { - spans: Vec::new() - } + StockSpanner { spans: Vec::new() } } fn next(&mut self, price: i32) -> i32 { let mut days = 1; @@ -23,12 +34,18 @@ impl StockSpanner { break; } } - self.spans.push(Span{price, days}); + self.spans.push(Span { price, days }); days } } fn main() { - let obj = StockSpanner::new(); - let ret_1: i32 = obj.next(price); + let mut obj = StockSpanner::new(); + println!("{}", obj.next(100)); + println!("{}", obj.next(80)); + println!("{}", obj.next(60)); + println!("{}", obj.next(70)); + println!("{}", obj.next(60)); + println!("{}", obj.next(75)); + println!("{}", obj.next(85)); } |