aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--online_stock_span.c85
-rw-r--r--online_stock_span.cpp20
-rw-r--r--online_stock_span.py33
-rw-r--r--online_stock_span.rs33
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));
}