【JavaScript】LeetCode：76-80

76 有效的括号

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

/**
 * @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中的最小值。

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. 如果是字母，就拼接当前段的字符串。

/**
 * @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。

/**
 * @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。

/**
 * @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;   
};