如何使用栈解决股票跨度(Stock Span)问题？C语言实现报错求助

错误原因 #

你代码的核心问题出在spans函数的取值逻辑：栈中存储的是「前一个更高价的下标值」，你两处错误使用了栈顶指针A->top本身，而非栈顶位置存储的下标值A->elem[A->top]。

1. while循环的判断条件，错误用A->top当下标取值
2. 计算S[i]时，错误用A->top当被减数

具体修改 #

将spans函数的逻辑修正为：

void spans(StackType *A, int X[], int S[]) {
    for (int i = 0; i < SIZE; i++) {
        // 修正判断条件：取栈顶存储的下标对应的价格比较
        while (!isEmpty(A) && (X[A->elem[A->top]] <= X[i]))
            pop(A);
        if (isEmpty(A))
            S[i] = i + 1;
        else
            // 修正计算逻辑：用栈顶存储的下标做减法
            S[i] = i - A->elem[A->top];
        push(A, i);
    }
    while (!isEmpty(A))
        pop(A);
    return;
}

逻辑验证 #

栈的top变量仅用于标识栈顶在数组elem中的索引，elem[top]才是我们存储的目标下标值：

• 当i=3（对应价格10）时，栈顶存储的下标是2（对应价格40>10），正确计算为3-2=1
• 当i=7（对应价格40）时，栈顶存储的下标是6（对应价格50>40），正确计算为7-6=1
• 全部计算完成后输出结果为[1] [1] [2] [1] [2] [3] [6] [1]，符合预期。

修改后完整代码 #

#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->elem[A->top]] <= X[i]))
            pop(A);
        if (isEmpty(A))
            S[i] = i + 1;
        else
            S[i] = i - A->elem[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;
}

内容的提问来源于stack exchange，提问作者hansebong