Stack 栈

括号闭合问题

问题描述

给定一个只包括'('，')'，'{'，'}'，'['，']'的字符串s， 判断字符串是否有效。

有效字符串需满足：

• 左括号必须用相同类型的右括号闭合。
• 左括号必须以正确的顺序闭合。

如：

• 有效的字符串："()"、"()[]{}"、"{[]}"。
• 无效的字符串："(]"、"([)]"。

解法

function isStrValid (str) {
    const matches = ['()', '[]', '{}']
    const arr = []
    for (let i = 0, len = str.length; i < len; i++) {
        const char = str.charAt(i)
        if (arr.length === 0) {
            arr.push(char)
            continue
        }
        const last = arr[arr.length - 1]
        if (matches.includes(last + char)) {
            arr.pop()
            continue
        }
        arr.push(char)
    }
    return arr.length === 0
}

字符消消乐

问题描述

给定一个字符串，消除其中所有的字符串 ac 和 b，如果消掉之后获得的新字符串中仍存在可消内容则需要继续消，直到没有可继续消的字符串为止。

比如字符串 aaaaaaaaabbbbbbbcccccbbbbbcccc 经过处理后应该得到空字符串。

解决方案

function deleteMatchStr (str) {
    const arr = str.split('')
    const tempArr = []
    arr.forEach((item) => {
        const last = tempArr.length ? tempArr[tempArr.length - 1] : ''
        if (last + item === 'ac') {
            tempArr.pop()
            return
        }
        if (item !== 'b') {
            tempArr.push(item)
        }
    })
    return tempArr.join('')
}
deleteMatchStr('aaaaaaaaabbbbbbbcccccbbbbbcccc')

Monotone stack 单调栈

单调栈是一种特殊的栈结构，其内部元素的排序是单调朝一个方向的。 在许多数组的范围查询问题上，用上单调栈可显著降低时间复杂度——毕竟其时间复杂度只有O(N)。

去重返回最小数

这是LeetCode里的一道难度级别显示为中等的题目。

题目：给定一串数字, 去除字符串中重复的数字, 而且不能改变数字之间的顺序, 使得返回的数字最小 "23123" => "123" "32134323" => "1342"。

解法如下：

function handleArray(strings) {
    const array = strings.split('')
    const stack = []
    const obj = {}

    for (let i = 0, len = array.length; i < len; i++) {
        const item = array[i]
        if (stack.length === 0) {
            stack.push(item)
            continue
        }
        const lastStackItem = stack[stack.length - 1]
        while (lastStackItem >= item && array.slice(i).includes(lastStackItem)) {
            stack.pop()
        }
        if (!stack.includes(item)) {
            stack.push(item)
        }
    }

    return stack.join('')
}
handleArray('23123')
handleArray('32134323')