leetcode-hot100-12栈

leetcode100题文章目录leetcode100题1.栈20.有效的括号方法一：c方法一：js方法一：java155.最小栈方法一：c方法一：js方法一：java394.字符串解码方法一：c方法一：js方法一：java739.每日温度方法一：c方法一：js方法一：java方法二：c（暴力求解：超时）方法二：js方法二：java84.柱状图中最大的矩形方法一：c方法一：js方法一：java1.栈20.有效的括号给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。**输入：**s = “()”**输出：**true方法一：cclass Solution{public:boolisValid(string s){intn=s.size();// 获取字符串长度if(n%2)returnfalse;// 长度为奇数直接返回false，括号必须成对出现stackcharstk;// 定义栈存储左括号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;// 遍历结束栈空则所有括号匹配，否则不合法}};方法一：jsvarisValid=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;// 栈空则全部匹配，否则不合法};方法一：javaclassSolution{publicbooleanisValid(Strings){intn=s.length();// 获取字符串长度if(n%2!=0)returnfalse;// 长度奇数直接返回false，括号成对出现StackCharacterstack=newStack();// 初始化栈存储左括号for(inti=0;in;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]方法一：cclass MinStack{public:stackpairint,intstk;// 栈元素为pair：first存储原值，second存储当前栈内最小值MinStack(){stk.push({0,INT_MAX});// 初始化栈，放入哨兵节点，默认最小值为int最大值}voidpush(intval){stk.push({val,min(getMin(),val)});// 入栈：存入当前值+当前栈最新最小值}voidpop(){stk.pop()