javascript">/*** @param {string} s* @return {boolean}*/varisValid=function(s){let st =[];for(let i of s){if(i =='('){st.push(')');}elseif(i =='{'){st.push('}');}elseif(i =='['){st.push(']');}elseif(i == st[st.length -1]){st.pop();}elseif(st.length ==0|| i != st[st.length -1]){returnfalse;}}return st.length ==0;};
77 最小栈
栈
增加一个辅助栈:minst,栈顶元素放置栈st中的最小值。
push():若push进来的数 <= minst的栈顶元素,则将该数加入minst中。
pop():若要pop的数 = minst的栈顶元素,则同时将minst.pop()。
保证minst的栈顶元素始终是st中的最小值。
javascript">varMinStack=function(){this.st =[];this.minst =[];};/** * @param {number} val* @return {void}*/MinStack.prototype.push=function(val){this.st.push(val);if(this.minst.length ==0|| val <=this.minst[this.minst.length -1]){this.minst.push(val);}};/*** @return {void}*/MinStack.prototype.pop=function(){if(this.st.pop()==this.minst[this.minst.length -1]){this.minst.pop();}};/*** @return {number}*/MinStack.prototype.top=function(){returnthis.st[this.st.length -1];};/*** @return {number}*/MinStack.prototype.getMin=function(){returnthis.minst[this.minst.length -1];};/*** Your MinStack object will be instantiated and called as such:* var obj = new MinStack()* obj.push(val)* obj.pop()* var param_3 = obj.top()* var param_4 = obj.getMin()*/
78 字符串解码
栈
num:存放当前括号前的数字,注意:可能是多位数。
res:存放当前括号中的字母。
st:栈中存放[num,前一个括号到当前括号之间的res]。
遍历字符串数组:
如果是数字,则num中存数字。
如果是"[",则将num和前一段的字符串入栈。
如果是"]",则栈顶元素出栈,将前一段的字符串和num个该段字符串拼接。
如果是字母,就拼接当前段的字符串。
javascript">/*** @param {string} s* @return {string}*/vardecodeString=function(s){let st =[];let res ="";let num =0;for(let i of s){if(!isNaN(i)){num = num *10+Number(i);}elseif(i =="["){st.push([num, res]);res ="";num =0;}elseif(i =="]"){let tmp = st.pop();res = tmp[1]+ res.repeat(tmp[0]);}else{res += i;}}return res;};
javascript">/*** @param {number[]} heights* @return {number}*/varlargestRectangleArea=function(heights){let st =[];let res =0;heights.unshift(0);heights.push(0);st.push(0);for(let i =1; i < heights.length; i++){if(heights[i]>= heights[st[st.length -1]]){st.push(i);}else{while(heights[i]< heights[st[st.length -1]]){let h = heights[st[st.length -1]];st.pop();let w = i - st[st.length -1]-1;res = Math.max(res, h * w);}st.push(i);}}return res;};