有人相爱，有人夜里开车看海，我是leetcode第一题都做不出来

这是LeetCode的第20题：有效的括号

前几天解这道算法题，没有解出来，也不理解官方为何把左括号作为值，右括号作为键，看着极为别扭；今天也无心工作，仔细研究，利用自己的方法把这道题的破解出来了，思路也理清晰了

顿时信心大增

上着班就把解题思路给写出来了，供大家参考

有效的括号

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

有效字符串需满足：

1. 左括号必须用相同类型的右括号闭合。
2. 左括号必须以正确的顺序闭合。
3. 每个右括号都有一个对应的相同类型的左括号。  

示例 1：

输入：s = "()"

输出：true

示例 2：

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

输出：true

示例 3：

输入：s = "(]"

输出：false

解题思路

根据有效字符串的要求我们可以知道，这个字符串的长度肯定是偶数，当有一个左括号时下一个应该是与其匹配的右括号或者是左括号

此时我们利用栈的先进后出，只能栈顶元素出来的特点来解决它

不了解栈的朋友可以看这一片文章：栈,队列和链表三者之间的关系与区别

遍历字符串时，当遇到一个左括号，我们会期望在后续的遍历中，有一个相同类型的右括号将其闭合。由于后遇到的左括号要先闭合，因此我们可以将这个左括号放入栈顶。

左括号入栈： 遇到右括号时，匹配栈顶元素，符合则出栈：

当遇到一个右括号时，此时可以取出栈顶的左括号并判断它们是否是相同类型的括号。如果不是相同的类型，或者栈中并没有左括号了，那么字符串 s无效，则返回false。如果字符串遍历到最后，栈为空则证明这个字符串是有效括号

为了判断当前字符是左括号还是右括号，可以使用map结构来先存储配对的括号，把左括号作为键,右括号作为值

具体解题步骤我们可以分为一下几步：

• 第一步：判断字符串的长度是不是偶数，如果不是则直接返回false

• 第二步：初始化一个map，把左括号作为键,右括号作为值；再初始化一个空栈stack,用来存放左括号。

• 第三步：遍历字符串，获取当前值

• 第四步：判断当前值，是不是map里的键（左括号）,如果是则把当前值入栈；如果不是则把栈顶元素作为键取出map的值，如果和当前字符相同，则就证明是一个有对括号可以把栈顶元素删除,然后继续进行第三步第四步操作；如果不一样则就返回false。

• 第五步：当栈为空时，说明这是有效字符串，返回true，否则返回false

var isValid = function(s) {
    if(s.length%2 === 1) return false
    // 初始化一个map结构
    let map = new Map([
        ['(',')'],
        ['[',']'],
        ['{','}']
    ])
    // 初始化一个栈用来存放 左括号
    let stack= []
    for(let current of s){
        if(map.has(current)){
            // 左括号 入栈
            stack.push(current)
        }else{
            // 当前右括号 与栈顶元素匹配
            if(current === map.get(stack[stack.length-1])){
                stack.pop()
            }else{
                return false
            }
        }
    }
    // 长度为0返回true,栈内还有内容就返回false
    return !stack.length
};

知识点

• map初始化：Map 函数可以接受一个数组作为参数，用来进行初始化。但是跟 Set 不同的是，Map 中该数组中的成员是一对对表示键值对的数组（或有点类似数组的对象）。

let map = new Map([
     // [键 , 值]
        ['(',')'],
        ['[',']'],
        ['{','}']
    ])

has()方法判断map里有没有这一个键

get()方法获取map里当前键对应的值