LeetCode题解之有效的括号(栈)

前言

说完了链表，题解我们再看看栈。有栈

理解栈

栈是括号什么，很金典的题解比喻就是把 栈 比喻成叠盘子，一个个叠上去，有栈然后拿的括号时候会先拿最上面的，也就是题解最后叠上去的那个。

先进者后出、有栈后进者先出，括号这就是题解栈结构。

实际应用

那么栈在实际应用中有什么场景呢?有栈

可太多了，比如Activity中的括号任务栈，编译器实现方法表达式，题解浏览器的有栈前进后退。

这里拿浏览器的括号前进后退做例子。

在浏览器中，每打开一个页面，就把这个页面入栈，然后点击后退的时候就将页面出栈。这是不是挺像Activity页面的云南idc服务商任务栈的。 如果有前进功能，那么就再需要一个栈，当点击后退的时候，就把页面从A栈出，然后进入B栈，这样点击前进的时候，就能从B栈重新回到A栈了。

1)浏览网页，每打开一个网页就入栈A。比如这里打开了网页M和网页N。

2)点击后退，网页N出栈A，入栈B。

3)点击前进，网页N出栈B，入栈A。

Java中的栈类

在Java中，栈的对应类为Stack。

//初始化栈 Stack<String> stack =new Stack<String>(); //入栈 stack.push("test"); //出栈，返回出栈的元素 String str=stack.pop(); 

算法题

还是老样子，来一题栈相关的算法题。

题目

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

有效字符串需满足：

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

示例 1：输入：s = "()" 输出：true

示例 2：输入：s = "()[]{ }" 输出：true

示例 4：输入：s = "([)]" 输出：false

示例 5：输入：s = "{ []}" 输出：true

解法

解法就是利用栈了。

遇到左括号入栈，遇到右括号就把相应的左括号出栈，如果右括号和要出栈的这个元素不一致，就说明括号没有成对。

关于左括号和右括号的对应关系，可以用HashMap来存储，来一起看看：

public boolean isValid(String s) {          int n = s.length();         if (n % 2 == 1) {              return false;         }         Map<Character, Character> pairs = new HashMap<Character, Character>() { {              put(), ();             put(], [);             put(}, { );         }};         Deque<Character> stack = new LinkedList<Character>();         for (int i = 0; i < n; i++) {              char ch = s.charAt(i);             if (pairs.containsKey(ch)) {                  if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {                      return false;                 }                 stack.pop();             } else {                  stack.push(ch);             }         }         return stack.isEmpty();     } 

也有比较灵活的办法，就是入栈的时候就确定好括号的对应关系，直接入栈左括号对应的右括号。

public boolean isValid(String s) {          if(s.isEmpty())             return true;         Stack<Character> stack=new Stack<Character>();         for(char c:s.toCharArray()){              if(c==()                 stack.push());             else if(c=={ )                 stack.push(});             else if(c==[)                 stack.push(]);             else if(stack.empty()||c!=stack.pop())                 return false;         }         if(stack.empty())             return true;         return false;     } 

时间复杂度

需要遍历字符串，所以时间复杂度为 O(n)

空间复杂度

栈的字符数量最大为n，Map数量为3，高防服务器所以空间复杂度就是O(n)

参考

https://time.geekbang.org/column/article/41222

本文转载自微信公众号「码上积木」，可以通过以下二维码关注。转载本文请联系码上积木公众号。