leetcode-hot100-12栈

leetcode100题

1.栈

20.有效的括号

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

有效字符串需满足：

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

**输入：**s = “()”

**输出：**true

方法一：c

class Solution{public:boolisValid(string s){intn=s.size();// 获取字符串长度if(n%2)returnfalse;// 长度为奇数直接返回false，括号必须成对出现stack<char>stk;// 定义栈存储左括号for(autoc:s)// 遍历字符串每个字符{if(c=='('||c=='['||c=='{')stk.push(c);// 左括号直接入栈else// 右括号执行匹配逻辑{if(stk.size()==0)returnfalse;// 栈空无左括号匹配，直接不合法if(stk.top()=='('&&c==')')stk.pop();// 小括号匹配，弹出栈顶左括号elseif(stk.top()=='['&&c==']')stk.pop();// 中括号匹配，弹出栈顶左括号elseif(stk.top()=='{'&&c=='}')stk.pop();// 大括号匹配，弹出栈顶左括号elsereturnfalse;// 括号类型不匹配，直接不合法}}returnstk.size()==0;// 遍历结束栈空则所有括号匹配，否则不合法}};

方法一：js

varisValid=function(s){constn=s.length;// 获取字符串长度if(n%2)returnfalse;// 长度奇数直接返回false，括号必须成对conststack=[];// 定义数组模拟栈存储左括号for(constcofs){// 遍历字符串每个字符if(c==='('||c==='['||c==='{')stack.push(c);// 左括号入栈else{// 右括号执行匹配逻辑if(stack.length===0)returnfalse;// 栈空无左括号匹配，不合法if(stack[stack.length-1]==='('&&c===')')stack.pop();// 小括号匹配，弹出栈顶elseif(stack[stack.length-1]==='['&&c===']')stack.pop();// 中括号匹配，弹出栈顶elseif(stack[stack.length-1]==='{'&&c==='}')stack.pop();// 大括号匹配，弹出栈顶elsereturnfalse;// 括号类型不匹配，直接不合法}}returnstack.length===0;// 栈空则全部匹配，否则不合法};

方法一：java

classSolution{publicbooleanisValid(Strings){intn=s.length();// 获取字符串长度if(n%2!=0)returnfalse;// 长度奇数直接返回false，括号成对出现Stack<Character>stack=newStack<>();// 初始化栈存储左括号for(inti=0;i<n;i++){// 遍历字符串每个字符charc=s.charAt(i);// 获取当前字符if(c=='('||c=='['||c=='{')stack.push(c);// 左括号入栈else{// 右括号执行匹配逻辑if(stack.isEmpty())returnfalse;// 栈空无左括号匹配，不合法if(stack.peek()=='('&&c==')')stack.pop();// 小括号匹配，弹出栈顶elseif(stack.peek()=='['&&c==']')stack.pop();// 中括号匹配，弹出栈顶elseif(stack.peek()=='{'&&c=='}')stack.pop();// 大括号匹配，弹出栈顶elsereturnfalse;// 括号类型不匹配，直接不合法}}returnstack.isEmpty();// 遍历结束栈空则合法，否则不合法}}

155.最小栈

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

实现MinStack类:

• MinStack()初始化堆栈对象。
• void push(int val)将元素val推入堆栈。
• void pop()删除堆栈顶部的元素。
• int top()获取堆栈顶部的元素。
• int getMin()获取堆栈中的最小元素。

输入：["MinStack","push","push","push","getMin","pop","top","getMin"][[],[-2],[0],[-3],[],[],[],[]]输出：[null,null,null,null,-3,null,0,-2]

方法一：c

class MinStack{public:stack<pair<int,int>>stk;// 栈元素为pair：first存储原值，second存储当前栈内最小值MinStack(){stk.push({0,INT_MAX});// 初始化栈，放入哨兵节点，默认最小值为int最大值}voidpush(intval){stk.push({val,min(getMin(),val)});// 入栈：存入当前值+当前栈最新最小值}voidpop(){stk.pop()