【JavaScript】LeetCode：76-80

文章目录

76 有效的括号
77 最小栈
78 字符串解码
79 每日温度
80 柱形图中最大的矩形

76 有效的括号

在这里插入图片描述

栈
三种不匹配的情况：
1. ( [ { } ] ( )，最左边的"("多余，即字符串遍历完了，栈还不为空。
2. [ { ( } } ]，中间"( }"不匹配。
3. [ { } ] ( ) ) )，右边三个")"多余，即字符串还未遍历完，栈空了。
如果遇见左括号，就将对应类型的右括号入栈，方便遇见右括号时进行匹配。
如果遇见右括号，就与栈顶元素进行比较，相同则将栈顶元素出栈，不同则返回false。
在此基础上还可以剪枝操作：if(s.length % 2 != 0) return false;，如果括号的数量是奇数，直接返回false。

javascript">/*** @param {string} s* @return {boolean}*/
var isValid = function(s) {let st = [];for(let i of s){if(i == '('){st.push(')');}else if(i == '{'){st.push('}');}else if(i == '['){st.push(']');}else if(i == st[st.length - 1]){st.pop();}else if(st.length == 0 || i != st[st.length - 1]){return false;}}return st.length == 0;
};

77 最小栈

在这里插入图片描述

栈
增加一个辅助栈：minst，栈顶元素放置栈st中的最小值。
push()：若push进来的数 <= minst的栈顶元素，则将该数加入minst中。
pop()：若要pop的数 = minst的栈顶元素，则同时将minst.pop()。
保证minst的栈顶元素始终是st中的最小值。

javascript">var MinStack = 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() {return this.st[this.st.length - 1];
};/*** @return {number}*/
MinStack.prototype.getMin = function() {return this.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]。
遍历字符串数组：
1. 如果是数字，则num中存数字。
2. 如果是"["，则将num和前一段的字符串入栈。
3. 如果是"]"，则栈顶元素出栈，将前一段的字符串和num个该段字符串拼接。
4. 如果是字母，就拼接当前段的字符串。

javascript">/*** @param {string} s* @return {string}*/
var decodeString = function(s) {let st = [];let res = "";let num = 0;for(let i of s){if(!isNaN(i)){num = num * 10 +  Number(i);}else if(i == "["){st.push([num, res]);res = "";num = 0;}else if(i == "]"){let tmp = st.pop();res = tmp[1] + res.repeat(tmp[0]);}else{res += i;}}return res;
};

79 每日温度

在这里插入图片描述

单调栈
单调递增栈：求左 / 右第一个比当前元素（栈顶元素）大的位置。
单调递减栈：求左 / 右第一个比当前元素（栈顶元素）小的位置。
此题需构造一个单调递增栈st，栈中存储元素对应的下标。
单调栈是为了存放之前遍历过的元素。
遍历温度数组，若当前元素 > 栈顶元素，则记录结果，栈顶元素出栈，当前元素入栈；若当前元素 <= 栈顶元素，当前元素入栈。
结果数组res可以初始化为0，以便于如下情况：温度数组遍历完成后，栈中仍然有元素，此时栈中元素的后面都没有比自己大的值，对应的结果应该为0。

javascript">/*** @param {number[]} temperatures* @return {number[]}*/
var dailyTemperatures = function(temperatures) {let answer = Array(temperatures.length).fill(0);let st = [];st.push(0);for(let i = 1; i < temperatures.length; i++){if(temperatures[i] <= temperatures[st[st.length - 1]]){st.push(i);}else{while(st.length != 0 && temperatures[i] > temperatures[st[st.length - 1]]){answer[st[st.length - 1]] = i - st[st.length - 1];st.pop();}st.push(i);}}return answer;
};

80 柱形图中最大的矩形

在这里插入图片描述

单调栈
技巧：heights数组首尾各加一个0，以便于第一个数和最后一个数计算矩形面积。
此题需构造一个单调递减栈st，栈中存储元素对应的下标。
遍历柱状图数组，若当前元素 >= 栈顶元素，当前元素入栈；若当前元素 < 栈顶元素，计算矩形面积并更新最大值。
如果当前元素 < 栈顶元素，说明此时以栈顶元素为基准，左、右两端的矩形高度均小于栈顶元素的高度，此时应计算矩形面积，高h = 栈顶元素对应的高度，宽w = 当前元素的下标 - 下一个栈顶元素中存放的下标 - 1，面积s = h * w。

javascript">/*** @param {number[]} heights* @return {number}*/
var largestRectangleArea = 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;   
};