单调栈

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

英语学习:

  • 时间复杂度:time complexity
  • 单调栈:monotone stack

1、介绍

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

2、去重返回最小数

这是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
        }
        while (stack[stack.length - 1] >= item && array.slice(i).includes(stack[stack.length - 1])) {
            stack.pop()
        }
        if (!stack.includes(item)) {
            stack.push(item)
        }
    }

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

3、参考资料

Was this helpful?

0 / 0

发表评论 0

Your email address will not be published. Required fields are marked *