栈

先来看一道题

Leetcode 32 Longest Valid Parentheses (最长有效括号)

给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"

示例 2:

输入: ")()())"
输出: 4
解释: 最长有效括号子串为 "()()"

这道题可以用动态规划来做，也能用简洁明了的栈来解决。

什么是栈？

栈是一种先进后出（LIFO）的有序集合，新添加的元素在栈顶，旧元素在栈底。

以下图为例，1、2、3、4、5、6、7先后进栈：

创建栈

创建一个类来表示栈：

class Stack { // 初始化类，创建数组 items 存放入栈元素 constructor() { this.items = []; } // push 方法进行元素入栈（可同时入栈一或多个元素），无返回值 push() { this.items.push(...arguments); } // pop 方法出栈一个元素，返回出栈元素 pop() { return this.items.pop(); } // peek 方法返回栈顶元素，不对栈本身做任何操作 peek() { return this.items[this.items.length-1]; } // size 方法返回栈内元素个数 size() { return this.items.length; } // isEmpty 方法查看栈是否为空，返回布尔值 isEmpty() { return this.items.length == 0; } // clear 方法清空栈，无返回值 clear() { this.items = []; } // print 方法打印栈内元素 print() { console.log(this.items.toString()); }} // 测试 let stack = new Stack();stack.push(1,2,3,4);stack.print(); // 1,2,3,4stack.isEmpty(); // falsestack.size(); // 4stack.pop(); // 4stack.peek(); // 3stack.clear();

注意

因为 JavaScript 的类内暂时无法定义私有成员，所以可以在类外访问到存储栈元素的数组 items，这个操作是很危险的。

stack.items; // [1, 2, 3, 4]

这时可以使用闭包和IIFE进行避免，这是一个很无奈的办法：

let Stack = (function () { // 使用 WeakMap 存储数组（数组存放进栈元素） let items = new WeakMap(); class Stack { constructor() { items.set(this, []); } push() { items.get(this).push(...arguments); } // 其他方法 } return Stack;})(); let s = new Stack();// 无法访问到 itemss.items; // undefined

WeakMap: WeakMap是类似Map的键值对集合，但WeakMap的键是弱引用的，只要不存在引用，垃圾回收机制就会回收掉占用的内存，相当于自动删除，而不用手动删除。

用栈解题

思路：

变量start存放有效括号起始下标，maxLen存放最大长度；

栈只存放左括号的下标，遇到左括号，将其下标存入栈中；

遇到右括号，若此时栈为空，跳过本次循环并更新start；若栈不为空，则栈顶元素出栈；

栈顶元素出栈后，若栈为空，则计算当前下标和start的距离，并更新maxLen；

栈顶元素出栈后，若栈不为空，则计算当前下标和栈顶存放的下标的距离，并更新maxLen；

循环遍历直至结束。

function test(str) { let stack = new Stack(); let start = 0; let maxLen = 0; for(let i=0; i<str.length; i++) { // 如果是左括号，下标入栈 if (str[i] == '(') { stack.push(i); } else { // 如果是右括号 if (stack.isEmpty()) { start = i+1; continue; } else { // 栈内不为空，则出栈一个左括号进行匹配 stack.pop(); // 栈顶元素出栈后，栈为空 if (stack.isEmpty()) { // 根据当前下标和 start 去更新 maxLen maxLen = Math.max(maxLen, i-start+1); } else { // 栈不为空，根据当前下标和栈顶存放的下标去更新 maxLen maxLen = Math.max(maxLen, i-stack.peek()); } } } } return maxLen;} test('(()'); // 2test(')()())'); // 4