当前位置:   article > 正文

LeetCode //C - 901. Online Stock Span

LeetCode //C - 901. Online Stock Span

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.

  • For example, if the prices of the stock in the last four days is [7,2,1,2] and the price of the stock today is 2, then the span of today is 4 because starting from today, the price of the stock was less than or equal 2 for 4 consecutive days.
  • Also, 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.

Implement the StockSpanner class:

  • StockSpanner() Initializes the object of the class.
  • int next(int price) Returns the span of the stock’s price given that today’s price is price.
     
Example 1:

Input:
[“StockSpanner”, “next”, “next”, “next”, “next”, “next”, “next”, “next”]
[[], [100], [80], [60], [70], [60], [75], [85]]
Output:
[null, 1, 1, 1, 2, 1, 4, 6]
Explanation
StockSpanner stockSpanner = new StockSpanner();
stockSpanner.next(100); // return 1
stockSpanner.next(80); // return 1
stockSpanner.next(60); // return 1
stockSpanner.next(70); // return 2
stockSpanner.next(60); // return 1
stockSpanner.next(75); // return 4, because the last 4 prices (including today’s price of 75) were less than or equal to today’s price.
stockSpanner.next(85); // return 6

Constraints:
  • 1 < = p r i c e < = 1 0 5 1 <= price <= 10^5 1<=price<=105
  • At most 1 0 4 10^4 104 calls will be made to next.

From: LeetCode
Link: 901. Online Stock Span


Solution:

Ideas:

This code defines a StockSpanner struct with three fields: prices and spans are dynamically allocated arrays to store the price and span of each stock, and top is used to keep track of the stack’s top element index. The stockSpannerCreate function initializes a StockSpanner object, stockSpannerNext processes the next stock price and calculates its span, and stockSpannerFree cleans up the allocated memory to prevent memory leaks.

Caode:
typedef struct {
    int* prices;
    int* spans;
    int top;
} StockSpanner;

StockSpanner* stockSpannerCreate() {
    StockSpanner* spanner = (StockSpanner*)malloc(sizeof(StockSpanner));
    spanner->prices = (int*)malloc(sizeof(int) * 10000); // Assuming at most 10^4 calls.
    spanner->spans = (int*)malloc(sizeof(int) * 10000);  // Same assumption as above.
    spanner->top = -1; // Initialize stack top as -1 indicating empty stack.
    return spanner;
}

int stockSpannerNext(StockSpanner* obj, int price) {
    int span = 1;
    while (obj->top >= 0 && obj->prices[obj->top] <= price) {
        span += obj->spans[obj->top]; // Add the span of elements that are less than or equal to the current price.
        obj->top--; // Pop the elements that are less than or equal to the current price.
    }
    obj->top++;
    obj->prices[obj->top] = price; // Push the current price onto the stack.
    obj->spans[obj->top] = span; // Push the current span onto the stack.
    return span;
}

void stockSpannerFree(StockSpanner* obj) {
    free(obj->prices); // Free the allocated memory for prices.
    free(obj->spans); // Free the allocated memory for spans.
    free(obj); // Finally, free the object itself.
}

/**
 * Your StockSpanner struct will be instantiated and called as such:
 * StockSpanner* obj = stockSpannerCreate();
 * int param_1 = stockSpannerNext(obj, price);
 * stockSpannerFree(obj);
 */
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/149234
推荐阅读
相关标签
  

闽ICP备14008679号