Leetcode~栈

Xherlock

2021 年 10 月 12 日

500 次浏览

暂无评论

2355字数

数据结构与算法

# Leetcode~栈

#### [20. 有效的括号](https://leetcode-cn.com/problems/valid-parentheses/)

题目：给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 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. 最小栈](https://leetcode-cn.com/problems/min-stack/)

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

法一：最好想，最慢

```C
#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，这样下来速度上来了

改动地方如下

```C
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;
}
```

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

最后修改：2021 年 10 月 25 日

如果觉得我的文章对你有用，请随意赞赏

Leetcode~栈

Xherlock • 2021 年 10 月 12 日

Leetcode~栈

发表评论取消回复

Reverse（十一）

Win11新机鼓捣记录

栈~数制转换

C++学习

Python实现文件管理系统（重命名和删除）

简单控件

为数据快速添加引号

Reverse（十一）

此内容被密码保护

位运算

Leetcode~栈

发表评论 取消回复

Leetcode~栈

发表评论取消回复