C语言算法-解答最长有效括号问题的C语言实现

题目

给定一个只包含 '(' 和 ')' 的字符串 s，找出其中最长的有效括号子串的长度。

引言

最长有效括号问题需要考虑括号匹配和子串长度的逻辑。我们可以使用栈的方法来解决这个问题，通过将括号的下标入栈，然后计算连续的有效括号子串长度。解决这个问题需要进行栈操作和子串长度的计算。

算法思路

我们将使用栈的方法来解决最长有效括号问题。

算法的步骤如下：

1. 定义一个栈 stack，用于记录括号的下标。
2. 初始化一个变量 maxLen 用于记录最长有效括号子串的长度，初始值为0。
3. 将栈底初始化为-1，表示栈中元素的下标差值为当前元素的下标与栈顶元素的下标差值，用于计算子串长度。

4. 遍历字符串 s，从第一个字符开始：

   • 如果字符是 '('，将其下标入栈。
   • 如果字符是 ')'，弹出栈顶元素，并计算当前有效子串的长度，更新 maxLen。
5. 返回 maxLen，即最长有效括号子串的长度。

代码实现

下面是使用C语言实现的代码：

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

typedef struct {
    int* data;
    int top;
} Stack;

void initStack(Stack* stack, int size) {
    stack->data = (int*)malloc(size * sizeof(int));
    stack->top = -1;
}

void push(Stack* stack, int value) {
    stack->data[++stack->top] = value;
}

int pop(Stack* stack) {
    return stack->data[stack->top--];
}

int isEmpty(Stack* stack) {
    return stack->top == -1;
}

int max(int a, int b) {
    return a > b ? a : b;
}

int longestValidParentheses(char* s) {
    int maxLen = 0;
    int sLen = strlen(s);

    Stack stack;
    initStack(&stack, sLen);

    push(&stack, -1);

    for (int i = 0; i < sLen; i++) {
        if (s[i] == '(') {
            push(&stack, i);
        } else {
            pop(&stack);
            if (isEmpty(&stack)) {
                push(&stack, i);
            } else {
                maxLen = max(maxLen, i - stack.data[stack.top]);
            }
        }
    }

    free(stack.data);

    return maxLen;
}

int main() {
    char s[] = "(()())";
    int result = longestValidParentheses(s);
    printf("String: %s\n", s);
    printf("Longest Valid Parentheses: %d\n", result);
    return 0;
}

算法分析

该算法只需要对字符串进行一次遍历，并进行栈操作和子串长度计算，所以时间复杂度为 O(n)，其中 n 是字符串的长度。

空间复杂度为 O(n)，算法使用了一个大小为 n 的栈。

示例和测试

示例输入:

String: "(()())"

示例输出:

Longest Valid Parentheses: 6

总结

本文使用C语言实现了解答最长有效括号问题的代码。通过使用栈的方法，我们能够找出给定字符串中最长的有效括号子串的长度。该算法的时间复杂度为 O(n)，空间复杂度为 O(n)。