Leetcode~栈

20. 有效的括号

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。

示例

输入：s = "()[]{}"
输出：true
输入：s = "([)]"
输出：false

bool isValid(char * s){
    char ch[10000];
    int top = 0;
    for(int i = 0; s[i]; i++){
        if(s[i] == '(' || s[i] == '[' || s[i] == '{')
            ch[top++] = s[i];
        else{
            if((--top)<0)
                return false;
            if(s[i] == ')' && ch[top] != '(')
                return false;
            if(s[i] == ']' && ch[top] != '[')
                return false;
            if(s[i] == '}' && ch[top] != '{')
                return false;
        }
    }
    return top?false:true;
}

155. 最小栈

题目：设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

法一：最好想，最慢

#include<stdio.h>
#include<malloc.h>

typedef struct MinStack{
    int data;
    struct MinStack *next;
} MinStack;

MinStack* minStackCreate() {
    MinStack *S = (MinStack *)malloc(sizeof(MinStack));
    S->next = NULL;
    return S;
}

void minStackPush(MinStack* obj, int val) {
    MinStack *p = (MinStack *)malloc(sizeof(MinStack));
    p->data = val;
    p->next = obj->next;
    obj->next = p;
}

void minStackPop(MinStack* obj) {
    MinStack *p;
    p = obj->next;
    obj->next = p->next;
    free(p);
}

int minStackTop(MinStack* obj) {
    return obj->next->data;
}

// 使用最简单的循环遍历，故花费时间较长
int minStackGetMin(MinStack* obj) {
    int min = obj->next->data;
    obj = obj->next;
    while(obj)
    {
        if(obj->data < min)
            min = obj->data;
        obj = obj->next;
    }
    return min;
}

void minStackFree(MinStack* obj) {
    MinStack *p = obj;
    while(obj)
    {
        p = obj->next;
        free(obj);
        obj = p;
    }
}

int main(void)
{
    MinStack *obj = minStackCreate();
    minStackPush(obj, -2);
    minStackPush(obj, 0);
    minStackPush(obj, -3);
    printf("%d\n", minStackGetMin(obj));
    minStackPop(obj);
    printf("%d\n", minStackTop(obj));
    printf("%d\n", minStackGetMin(obj));
}

法二：在法一基础上struct结构里增加一个min数据域，每次push入数字后，接收最小值，最后在getmin里直接获取头部next指针指向min，这样下来速度上来了

改动地方如下

typedef struct MinStack{
    int data;
    int min;    // 添加最小值域
    struct MinStack *next;
} MinStack;

// 每次入栈进行判断取最小值压入栈指针min的数据域
void minStackPush(MinStack* obj, int val) {
    MinStack *p = (MinStack *)malloc(sizeof(MinStack));
    p->data = val;
    if(obj->next==NULL)
        p->min = val;
    else
        if(val < obj->next->min)
            p->min = val;
        else
            p->min = obj->next->min;
    p->next = obj->next;
    obj->next = p;
}

int minStackGetMin(MinStack* obj) {
    return obj->next->min;
}

法三：在网上还看到有一种方法是一个栈一次入两个栈，第一次是该元素，第二次是最小值，也是可行的，基本思路与第二个差不多，不过感觉代码会不太好理解

持续更新……