aboutsummaryrefslogtreecommitdiff
path: root/online_stock_span.c
diff options
context:
space:
mode:
Diffstat (limited to 'online_stock_span.c')
-rw-r--r--online_stock_span.c85
1 files changed, 85 insertions, 0 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
+}