LeeCode-刷题日记-Day27

155. 最小栈

思路：创建一个最小值的栈，每次插入都把目前最小值存入栈中。出栈时，同步出栈，即可拿到当前栈的最小值。

var MinStack = function() {
    this.x_stack=[];
    this.min_stack=[Infinity]
};

/** 
 * @param {number} val
 * @return {void}
 */
MinStack.prototype.push = function(val) {
    this.x_stack.push(val);
    this.min_stack.push(Math.min(this.min_stack[this.min_stack.length-1],val));
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    this.x_stack.pop();
    this.min_stack.pop();
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.x_stack[this.x_stack.length-1];
};

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min_stack[this.min_stack.length-1];
};

1249. 移除无效的括号

思路：创建一个栈来存储，一个栈来存标记位。遍历字符串，寻找括号。遇到左右括号不匹配的情况将其入栈。左右括号匹配的情况将其出栈。最终遍历s，将其中在栈中的元素删除。

/**
 * @param {string} s
 * @return {string}
 */
var minRemoveToMakeValid = function(s) {
    let stack={},stackIndex=[];

    for(let i=0;i<s.length;i++){
        let item = s[i];
        if(!/[\(|\)]/.test(item)){
            continue;
        }
        //peek
        let peekIndex = stackIndex[stackIndex.length-1];
        let peek = stack[peekIndex];
        if(peek && item ===")"&&peek==="("){
            delete stack[peekIndex];
            stackIndex.pop();
        }else{
            stackIndex.push(i);
            stack[i]=item;
        }
    }
    return s.split("").filter((k,index)=>!stack[index]).join("");
};

1823. 找出游戏的获胜者

思路：将每个元素依次入栈，利用k跳转遍历。每次移除一个数。循环n-1次，最终在栈中的元素即使胜利者。

/**
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var findTheWinner = function(n, k) {
    let res=[];
    for(let i=1;i<=n;i++){
        res.push(i);
    }
    let index=0;
    for(let i=1;i<n;i++){
        index=(index+k-1)%res.length;
        res.splice(index,1)
    }
    return res.pop()
};