阅读 78

数据结构与算法leetcode题目解析-----栈(持续更新)

(声明:所有题目都是leetcode上非会员题目)

栈的定义

堆栈(stack)又称为栈或堆叠,是计算机科学中的一种抽象数据类型,只允许在有序的线性数据集合的一端(称为堆栈顶端top)进行加入数据(push)和移除数据(pop)的运算。因而按照后进先出(LIFO, Last In First Out)的原理运作。

Leetcode上栈相关的问题

leetcode 94, 144, 145. 二叉树的前中后序遍历

题目地址:二叉树的前序遍历 二叉树的中序遍历 二叉树的后序遍历

关于这三个二叉树最基本的问题,我在另一篇专栏里有详细给出使用栈完成非递归解法的全过程,这里不再列出,可以参考 二叉树前中后序遍历非递归实现(JavaScript)

leetcode 42. 接雨水

题目地址:接雨水

解法一. 暴力解法

/**
 * @param {number[]} height
 * @return {number}
 */
var trap = function(height) {
    let ans = 0;
    const size = height.length;
    for (let i = 1; i < size - 1; i++) {
        let max_left = 0, max_right = 0;
        for (let j = i; j >= 0; j--) { //Search the left part for max bar size
            max_left = Math.max(max_left, height[j]);
        }
        for (let j = i; j < size; j++) { //Search the right part for max bar size
            max_right = Math.max(max_right, height[j]);
        }
        ans += Math.min(max_left, max_right) - height[i];
    }
    return ans;
};
复制代码

解法二. 使用栈

/**
 * @param {number[]} height
 * @return {number}
 */
// 我们在遍历数组时维护一个栈。如果当前的条形块小于或等于栈顶的条形块,我们将条形块的索引入栈,意思是当前的条形块被栈中的前一个条形块界定。如果我们发现一个条形块长于栈顶,我们可以确定栈顶的条形块被当前条形块和栈的前一个条形块界定,因此我们可以弹出栈顶元素并且累加答案到ans。
var trap = function(height) {
    const len = height.length
    const stack = [];
    let ans = 0, current = 0;
    while (current < len) {
        // 如果栈不为空,且栈顶元素对应的柱子高度比当前柱子高度小
        // 当前栈顶柱子能够容纳的水等于这个柱子左边的柱子和右边的柱子包含区间的空间
        while (stack.length && height[current] > height[stack[stack.length - 1]]) {
            const top = stack.pop();
            if (!stack.length)
                break;
            const distance = current - stack[stack.length - 1] - 1;
            const bounded_height = Math.min(height[current], height[stack[stack.length - 1]]) - height[top];
            ans += distance * bounded_height;
        }
        // 栈中保存的是柱子的索引
        stack.push(current++);
    }
    return ans;
};
复制代码

leetcode 155. 最小栈

题目地址:最小栈

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []
    this.min = Infinity
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.min = Math.min(x, this.min)
    this.stack.push(x)
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    if (this.stack.length) {            
        if (this.min === this.stack[this.stack.length - 1]) {            
            this.stack.pop() 
            this.min = Infinity
            this.stack.forEach(item => {
            this.min = Math.min(this.min, item)
            }) 
        } else {
            this.stack.pop()
        }
    }
};

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

/**
 * @return {number}
 */
MinStack.prototype.getMin = function() {
    return this.min
};
复制代码

leetcode 225. 用队列实现栈

题目地址:用队列实现栈

/**
* Initialize your data structure here.
*/
var MyStack = function() {
    this.queue = []
};

/**
* Push element x onto stack. 
* @param {number} x
* @return {void}
*/
MyStack.prototype.push = function(x) {
    this.queue.unshift(x)
};

/**
* Removes the element on top of the stack and returns that element.
* @return {number}
*/
MyStack.prototype.pop = function() {
    return this.queue.shift()
};

/**
* Get the top element.
* @return {number}
*/
MyStack.prototype.top = function() {
    return this.queue[0]
};

/**
* Returns whether the stack is empty.
* @return {boolean}
*/
MyStack.prototype.empty = function() {
    return this.queue.length === 0
};
复制代码

leetcode 232. 用栈实现队列

题目地址:用栈实现队列

/**
* Initialize your data structure here.
*/
var MyQueue = function() {
    this.stack = []
};

/**
* Push element x to the back of queue. 
* @param {number} x
* @return {void}
*/
MyQueue.prototype.push = function(x) {
    this.stack.push(x)
};

/**
* Removes the element from in front of queue and returns that element.
* @return {number}
*/
MyQueue.prototype.pop = function() {
    return this.stack.shift()
};

/**
* Get the front element.
* @return {number}
*/
MyQueue.prototype.peek = function() {
    return this.stack[0]
};

/**
* Returns whether the queue is empty.
* @return {boolean}
*/
MyQueue.prototype.empty = function() {
    return this.stack.length === 0
};
复制代码

leetcode 341. 扁平化嵌套列表迭代器

题目地址:扁平化嵌套列表迭代器

/**
 * @constructor
 * @param {NestedInteger[]} nestedList
 */
var NestedIterator = function(nestedList) {
    this.list = [];
    this.resetList(nestedList);
};


/**
 * @this NestedIterator
 * @returns {boolean}
 */
NestedIterator.prototype.hasNext = function() {
    return this.list.length > 0;
};

/**
 * @this NestedIterator
 * @returns {integer}
 */
NestedIterator.prototype.next = function() {
    return this.list.shift();
};

NestedIterator.prototype.resetList = function(arr) {
    for (let i = 0; i < arr.length; i++) {
        if (arr[i].isInteger())
            this.list.push(arr[i].getInteger())
        else
            this.resetList(arr[i].getList())
    }
}; 
复制代码

leetcode 394. 字符串解码

题目地址:字符串解码

/**
 * @param {string} s
 * @return {string}
 */
var decodeString = function(s) {
    let stack = []
    for (const char of s) {
        if (char !== ']') {
            stack.push(char)
            continue
        }
        let cur = stack.pop()
        let str = '' 
        while (cur !== '[') {
            str = cur + str
            cur = stack.pop()
        }
        let num = ''
        cur = stack.pop()
        while (!isNaN(cur)) {
            num = cur + num
            cur = stack.pop()
        }
        stack.push(cur)
        stack.push(str.repeat(num))
    }
    return stack.join('')
};
复制代码

leetcode 496. 下一个更大元素 I

题目地址:下一个更大元素 I

var nextGreaterElement = function(nums1, nums2) {
    const stack = [], map = new Map()
    for (const num of nums2) {
        while (stack.length && num > stack[0]) {
            map.set(stack.shift(), num)
        }
        stack.unshift(num)
    }
    while (stack.length) {
        map.set(stack.shift(), -1)
    }
    return nums1.map((num) => map.get(num))
};
复制代码

leetcode 682. 棒球比赛

题目地址:棒球比赛

/**
 * @param {string[]} ops
 * @return {number}
 */
var calPoints = function(ops) {
    const stack = []
    const len = ops.length
    let res = 0
    if (len) {
        for (let i = 0; i < len; i++) {
            const item = ops[i]
            let val = 0
            switch (item) {
                case '+':
                    val = stack[0] + stack[1]
                    break;
                case 'D':
                    val = stack[0] * 2
                    break;
                case 'C':
                    stack.shift()
                    break;
                default:
                    val = item * 1
                    break;
            }
            if (item !== 'C') {
                stack.unshift(val) 
            }
        }
        res = stack.reduce((a, b) => a + b)
    }
    return res
};
复制代码

leetcode 735. 行星碰撞

题目地址:行星碰撞

/**
 * @param {number[]} asteroids
 * @return {number[]}
 */
 var asteroidCollision = function(asteroids) {
    const len = asteroids.length
    const res = []
    for (let i = 0; i < len; i++) {
        const aster = asteroids[i]
        if (!res.length) {
           res.push(aster)
        } else {
            const pop = res[res.length - 1]
            if (pop < 0 || aster > 0) {
                res.push(aster)
            } else {
                if (pop + aster > 0) {
                    continue
                } else if (pop + aster < 0) {
                    res.pop()
                    i--
                } else if (pop + aster === 0) {
                    res.pop()
                }
            }
        }
    }
    return res
};
复制代码

leetcode 739. 每日温度

题目地址:每日温度

/**
 * @param {number[]} T
 * @return {number[]}
 */
var dailyTemperatures = function(T) {
    let len = T.length
    let res = new Array(len).fill(0)
    let stack = []
    for (let i = 0; i < len; i ++) {
        while (stack.length && T[i] > T[stack[stack.length - 1]]) {
            const index = stack.pop()
            res[index] = i - index
        }
        stack.push(i)
    }
    return res
};
复制代码

leetcode 844. 比较含退格的字符串

题目地址:比较含退格的字符串

/**
 * @param {string} S
 * @param {string} T
 * @return {boolean}
 */
var backspaceCompare = function(S, T) {
    const stackS = []
    const stackT = []
    const sLen = S.length
    const tLen = T.length
    if (sLen) {
        for (let i = 0; i < sLen; i++) {
        if (S[i] === '#') {
            stackS[0] && stackS.pop()
        } else {
            stackS.push(S[i])
        }
        }
    }
    if (tLen) {
        for (let i = 0; i < tLen; i++) {
        if (T[i] === '#') {
            stackT[0] && stackT.pop()
        } else {
            stackT.push(T[i])
        }
        }
    }
    return stackS.join('') === stackT.join('')
};
复制代码

leetcode 856. 括号的分数

题目地址:括号的分数

/**
 * @param {string} S
 * @return {number}
 */
// [(]                # 遇到 ( 往栈添加
// [(, (]             # 继续添加
// [(, 1]             # 遇到 ) 合成一个1
// [(, 1, (]          # 遇到 ( 往栈添加
// [(, 1, (, (]       # 继续添加
// [(, 1, (, 1]       # 遇到 ) 合成一个1
// [(, 1, 2]          # 遇到 ) ,结构就是(1), 所以计算的话是 1 * 2
// [6]                # 遇到 ) ,结构是(1,2), 所以计算的话是 (1 + 2) * 2
var scoreOfParentheses = function(S) {
    const stack = []
    const len = S.length
    for (let i = 0; i < len; i++) {
        // 如果是(直接入栈
        if (S[i] === '(') {
            stack.push('(')
        // 如果栈顶是(说明找到一个括号,把栈内括号替换为1
        } else if (stack[stack.length - 1] === '(') {
                stack.pop()
                stack.push(1)
        // 如果栈顶不是(,字符是),说明栈顶是数字
        } else {
            let a = stack.pop()
            let sum = 0
            // 累加()值
            while(a !== '(') {
                sum += a
                a = stack.pop()
            }
            // 外部()相当于乘以2
            stack.push(sum * 2)
        }
    }
    return stack.reduce((a, b) => a + b)
};
复制代码

leetcode 1047. 删除字符串中的所有相邻重复项

题目地址:删除字符串中的所有相邻重复项

/**
 * @param {string} S
 * @return {string}
 */
var removeDuplicates = function(S) {
    if (S.length < 2) {
        return S
    }
    const stack = []
    let i = 1
    stack.push(S[0])
    while (i < S.length) {
        // 如果栈顶元素和字符串首个字母相同,移除栈顶元素
        if (stack[stack.length - 1] === S[i]) {
            stack.pop()
        } else {
            stack.push(S[i])
        }
        i++
    }
    return stack.join('')
};
复制代码

leetcode 面试题59 - II. 队列的最大值

题目地址:队列的最大值

var MaxQueue = function() {
    this.queue = []
    // 最大值队列
    this.maxQueue = []
    this.mLen = 0
    this.qLen = 0
};

/**
 * @return {number}
 */
MaxQueue.prototype.max_value = function() {
    return this.mLen ? this.maxQueue[0] : -1
};

/** 
 * @param {number} value
 * @return {void}
 */
MaxQueue.prototype.push_back = function(value) {
    while (this.mLen && this.maxQueue[this.mLen - 1] < value) {
        this.maxQueue.pop()
        this.mLen --
    }
    this.maxQueue.push(value)
    this.queue.push(value)
    this.qLen ++
    this.mLen ++
};

/**
 * @return {number}
 */
MaxQueue.prototype.pop_front = function() {
    if (!this.qLen) {
        return -1
    }
    let value = this.queue[0]
    if (value === this.maxQueue[0]) {
        this.maxQueue.shift()
        this.mLen --
    }
    this.queue.shift()
    this.qLen --
    return value
};
复制代码