c - 如何使用堆栈解决库存跨度问题？

Question

我正在看this stock span problem :

The stock span problem is a financial problem where we have a series of n daily price quotes for a stock and we need to calculate the span of stock’s price for all n days.

The span S_i of the stock’s price on a given day i is defined as the maximum number of consecutive days just before the given day, for which the price of the stock on the current day is less than or equal to its price on the given day.

在 this description算法解释:

Computing Spans with a Stack

• We keep in a stack the indices of the last element that is taller when "looking back"
• We scan the array from left to right
  • Let 𝑖 be the current index
  • We pop indices from the stack until we find index 𝑗 such that 𝑋[𝑖] < 𝑋[𝑗]
  • We set 𝑆[𝑖] <= 𝑖 − 𝑗
  • We push 𝑖 onto the stack

示例的输出应该是 {1,1,2,1,2,3,6,1}，但我的代码输出 {1,1,2,2,2,3,6,7 }

#include <stdio.h>
#include <stdlib.h>

#define SIZE 8

typedef int element;
typedef struct StackType {
    element elem[SIZE];
    int top;
} StackType;

void init(StackType *A) {
    A->top = -1;
}

int isEmpty(StackType *A) {
    return A->top == -1;
}

int isFull(StackType *A) {
    return A->top == SIZE - 1;
}

void push(StackType *A, element i) {
    if (isFull(A)) {
        printf("FULL\n");
        return;
    }
    A->top++;
    A->elem[A->top] = i;
}

element pop(StackType *A) {
    if (isEmpty(A)) {
        printf("Empty\n");
        return 0;
    }
    element temp = A->elem[A->top];
    A->top--;
    return temp;    
}

void spans(StackType *A, int X[], int S[]) {
    for (int i = 0; i < SIZE; i++) {
        while (!isEmpty(A) && (X[A->top] <= X[i]))
            pop(A);
        if (isEmpty(A))
            S[i] = i + 1;
        else
            S[i] = i - (A->top);
        push(A, i);
    }
    while (!isEmpty(A))
        pop(A);
    return;
}

int main() {
    StackType A;
    init(&A);
    int X[SIZE] = { 60, 30, 40, 10, 20, 30, 50, 40 };
    int S[SIZE];
    spans(&A, X, S);
    for (int i = 0; i < SIZE; i++)
        printf("[%d] ", S[i]);  
    printf("\n");
    return 0;
}

我调试了函数void spans ，我看到A->top没有以正确的方式改变。例如，当 i = 2 , A->top应该是2 ，但实际上，A->top是 1 。函数 pop 似乎有问题和push ，但我找不到问题所在。

Answer 1

您的实现中的问题是 A->top 是一个索引，而不是存储在堆栈顶部的值。

所以我建议定义一个函数来从堆栈中检索顶部值:

element peek(StackType *A) {
    if (isEmpty(A)) {
        printf("Empty\n");
        return 0;
    }
    return A->elem[A->top];
}

然后在函数 spans 中将所有出现的 A->top 替换为 peek(A)。我还将 if...else 结构更改为三元运算符:

void spans(StackType *A, int X[], int S[]) {
    for (int i = 0; i < SIZE; i++) {
        while (!isEmpty(A) && (X[peek(A)] <= X[i]))
            pop(A);
        S[i] = i + (isEmpty(A) ? 1 : -peek(A));
        push(A, i);
    }
    while (!isEmpty(A))
        pop(A);
    return;
}

最后一句话:我不会在 main 中定义堆栈，而是在 spans 中定义堆栈。