(动画详解)LeetCode20.有效的括号

题目描述

20. 有效的括号 - 力扣（LeetCode）

解题思路

栈的方法

遍历整个字符串

当检测到左括号的时候，就让左括号入栈

当检测到右括号的时候，就让左括号出栈与右括号对比

如果相等则继续比较直到结束，如果不相等就直接返回false

当匹配到右括号但栈中已经没有相应的左括号与之对应时就说明右括号多于左括号，那么饭返回false

当遍历结束后如果发现栈中还有元素，那么说明左括号多于右括号，返回fasle

分析完之后，我们决定定义一个栈来完成这道题，下面是需要的函数

StackInit,用于初始化栈

StackDestroy，用于释放内存，其他语言不用考虑，这里用C语言来实现

StackPush,用于向栈顶推入数据

StackPop,用于弹出栈顶数据

StackTop，用于返回栈顶元素

动画详解

先以'('和')'为例进行演示，这是最简单的一种情况

接着我们来看一个比较复杂的场景

示例( ( [ [ ] ] ) )  

那么下面我们来分析失败的情况

示例  (  )  (  ]

下面我们来看看括号个数不一致的情况

第一种情况是左括号多于右括号

示例  (  (  (  )  )

接下来就是右括号多于左括号的情况了

示例  (  (  )  )  )

代码实现

// 创建栈
typedef char STDataType;

struct Stack
{
	STDataType* x;
	int top;
	int capacity;
};

typedef struct Stack ST;

void StackInit(ST* pst)
{
	assert(pst);
	pst->x = NULL;
	pst->capacity = 0;
	// top指向的是栈顶元素的下一个位置
	pst->top = 0;
	// top指向的是当前的栈的元素
	/*pst->top = -1;*/
}

void StackDestroy(ST* pst)
{
	assert(pst);
	free(pst->x);
	pst->x = NULL;
	pst->capacity = pst->top = 0;
}

// 获取栈顶元素
STDataType StackTop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	return pst->x[pst->top-1];
}

void StackPush(ST* pst, STDataType x)
{
	assert(pst);
	// 扩容
	// top和capacity相等时说明没有容量了
	if (pst->top == pst->capacity)
	{
		// 判断容量是否为空
		int newcapacity = pst->capacity==0 ? 4 : pst->capacity * 2;
		STDataType* new = (STDataType*)realloc(pst->x,newcapacity * sizeof(STDataType));
		if (new == NULL)
		{
			perror("realloc failed");
            return;
		}
		pst->x = new;
		pst->capacity = newcapacity;
	}
	pst->x[pst->top] = x;
	pst->top++;
}

// 出栈
void StackPop(ST* pst)
{
	assert(pst);
	assert(pst->top > 0);
	pst->top--;
}

// 判断栈是否为空
bool StackEmpty(ST* pst)
{
	assert(pst);
	return pst->top == 0;
}

bool isValid(char* s)
{
    ST st;
    StackInit(&st);
    // 遍历字符串，如果是左括号就入栈
    while(*s)
    {
        if((*s=='(')||(*s=='[')||(*s=='{'))
        {
            StackPush(&st,*s);
        }
        // 如果是右括号，那么就让左括号出栈，并且比较二者是否匹配
        else
        {
            // 判断栈是否为空，也就是右括号多于左括号
            if(StackEmpty(&st))
            {
                StackDestroy(&st);
                return false;
            }
            char top = StackTop(&st);
            StackPop(&st);
            //如果不匹配，那么就直接返回fasle
            if((top=='('&&*s!=')')
            ||(top=='['&&*s!=']')
            ||(top=='{'&&*s!='}'))
            {
                return false;
            }
            
        }
        s++;
    }

    bool ret = StackEmpty(&st);
    return ret;
    StackDestroy(&st);
    return 0;
}

复杂度分析

我们很容易发现，关于栈的几个函数时间复杂度都近似为O(1),而仅有isValid函数中存在while循环，所以这个代码的时间复杂度为O(n)

总结

Bye!!