有效的括号

怎样从“判断 "()[]{}" 是否有效括号串。”推导出 栈 · 括号匹配，并证明每次状态变化都不会漏掉答案？

中心结论：栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。

判断 "()[]{}" 是否有效括号串。

在本站主例中，判断 "()[]{}" 是否有效括号串。

算法最终需要得到或观察：全部匹配成功,栈空,返回 true。

每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。

暴力方案的价值是确认题意并提供正确性基线。它通常会覆盖所有候选， 但没有保存已经确认的信息，因此同一状态会被重新计算。

1. 1建模把输入翻译成“栈与队列轨道”，明确答案需要观察什么。
2. 2状态只维护 栈内容、扫描下标、当前字符。
3. 3转移每一步按照 栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。
4. 4收尾读取 全部匹配成功,栈空,返回 true。，并复核边界与复杂度。

入栈/入队的不是所有历史，而是未来仍需要的信息。

这道题不是为了记住一个组件名称，而是为了让状态具有可解释的语义：栈内容、扫描下标、当前字符。

遇到左括号就进栈push，遇到右括号并且栈顶为与之对应的左括号，就把栈顶元素出栈。最后看栈里面还有没有其他元素，如果为空，即匹配。

需要注意，空字符串是满足括号匹配的，即输出 true。

栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。

执行过程中持续维护：栈内容、扫描下标、当前字符。

正确性依赖以下不变量：栈中始终是尚未匹配的左括号,且顺序与扫描序一致。

面试时可以压缩为：栈:左括号入栈,右括号弹栈比对;最终栈必须空,O(n)。

落到当前题，执行机制可以压缩为：栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。每一次更新都必须保持核心不变量，而不是只让样例碰巧得到正确答案。

1. 1题目与输入判断 "()[]{}" 是否有效括号串。 因为：栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。
2. 2空栈准备匹配扫描每个字符。 因为：栈记录尚未闭合的左括号。
3. 3')' 与栈顶 '(' 匹配栈顶弹出。 因为：LIFO 保证嵌套正确。
4. 4预测下一步先不要看下一帧——根据当前不变量,预测算法接下来会怎么动。 因为：主动预测会暴露你对不变量的真实理解,比被动看动画有效得多。
5. 5']' 与栈顶 '[' 匹配栈顶弹出。 因为：LIFO 保证嵌套正确。
6. 6'{' 是左括号,入栈左括号入栈。 因为：后进的左括号要先闭合。
7. 7全部匹配扫描结束,检查栈是否为空。 因为：有效当且仅当栈最终为空。
8. 8收尾与复杂度全部匹配成功,栈空,返回 true。 因为：时间 O(n) · 空间 O(n)。栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。

代码窗口不会按容易漂移的固定数字行号硬绑动画，而是根据当前语义阶段， 在完整 Go 实现中定位选择、计算、写回或返回分支。当前变量与高亮行一起变化。

func isValid(s string) bool {
	// 空字符串直接返回 true
	if len(s) == 0 {
		return true
	}
	stack := make([]rune, 0)
	for _, v := range s {
		if (v == '[') || (v == '(') || (v == '{') {
			stack = append(stack, v)
		} else if ((v == ']') && len(stack) > 0 && stack[len(stack)-1] == '[') ||
			((v == ')') && len(stack) > 0 && stack[len(stack)-1] == '(') ||
			((v == '}') && len(stack) > 0 && stack[len(stack)-1] == '{') {
			stack = stack[:len(stack)-1]
		} else {
			return false
		}
	}
	return len(stack) == 0
}

func main() {
    // 1. 主例
    //    输入：mode="valid-parens", text="()[]{}"
    //    期望：全部匹配成功,栈空,返回 true。
    //
    // 2. 失败 / 未命中
    //    检查：扫完还有剩余左括号忘记判 false。
    //
    // 3. 边界
    //    空输入、单元素、最小合法规模，以及答案恰好落在边界的情况。
    //
    // 4. 迁移
    //    LC155 最小栈；LC394 字符串解码
}

Go 参考实现基于 halfrost/LeetCode-Go 的 MIT 许可代码整理，并按本站教学结构补充解释与动画映射。

1. 1题意判断 "()[]{}" 是否有效括号串。
2. 2重复每一步重新回看全部历史会重复；栈或队列只保存仍可能影响未来决策的状态。
3. 3优化栈存待匹配左括号;遇右括号弹栈比对类型,空栈或类型不符即 false。
4. 4证明栈中始终是尚未匹配的左括号,且顺序与扫描序一致。
5. 5复杂度时间 O(n)，空间 O(n)