栈·队列·字符串高频算法面试题整理（Kotlin 题解，含最优解与其他解法）

这是算法面试题整理的第二篇，承接上一篇 数组·链表·哈希·二叉树高频算法面试题整理，本篇聚焦栈、队列、字符串三类。它们背后有几个特别高频的”套路武器”：单调栈、单调队列、滑动窗口——掌握了它们，一大批看起来很难的题会瞬间变简单。

每题依旧遵循同一结构：题意与思路 → Kotlin 实现 → 对比非最优解 → 时空复杂度分析。原理层面还没打牢的同学，建议先读姊妹篇 一文通俗读懂常见数据结构。

栈（Stack）是”后进先出 LIFO”，队列（Queue）是”先进先出 FIFO”。Kotlin 里常用 ArrayDeque 同时充当栈和队列：addLast/removeLast 当栈用，addLast/removeFirst 当队列用。

一、栈

栈最擅长处理“就近匹配 / 就近比较”的问题：括号匹配、表达式求值、”找下一个更大的元素”（单调栈）都是它的主场。

1. 有效的括号（简单）

判断字符串是否是有效括号序列，如 "()[]{}" 有效，"(]" 无效。

最优解：栈。遇到左括号就入栈，遇到右括号就看栈顶是否是与之匹配的左括号——是则出栈，否则无效。最后栈空才有效。

/**
 * 判断括号序列是否有效。
 * Check whether the brackets are valid.
 * @param s 只含括号的字符串
 * @return Boolean 有效返回 true
 */
fun isValid(s: String): Boolean {
    val stack = ArrayDeque<Char>()
    val pairs = mapOf(')' to '(', ']' to '[', '}' to '{')
    for (c in s) {
        if (c in pairs) {
            // 右括号：栈顶必须是与之匹配的左括号
            if (stack.isEmpty() || stack.removeLast() != pairs[c]) return false
        } else {
            stack.addLast(c)  // 左括号入栈
        }
    }
    return stack.isEmpty()   // 全部匹配完栈应为空
}

• 时间 O(n)，空间 O(n)。

非最优解：反复替换。循环把 ()、[]、{} 替换成空串，直到不能再替换，最后看是否为空串。逻辑直观，但每次替换要扫描整个字符串，最坏 O(n²)，且依赖字符串替换 API，不如栈优雅。

2. 最小栈（简单）

设计一个栈，支持 push、pop、top，并能在 O(1) 时间内返回栈中最小元素。

最优解：辅助栈。用一个”最小值栈”与数据栈同步压弹，最小值栈的栈顶始终是当前数据栈里的最小值。

/**
 * 最小栈：O(1) 获取栈中最小元素。
 * A stack that returns its minimum element in O(1).
 */
class MinStack {
    private val data = ArrayDeque<Int>()
    private val mins = ArrayDeque<Int>()  // 辅助栈，栈顶始终是当前最小值

    fun push(value: Int) {
        data.addLast(value)
        // 新的最小值 = min(当前值, 之前的最小值)
        mins.addLast(if (mins.isEmpty()) value else minOf(value, mins.last()))
    }

    fun pop() {
        data.removeLast()
        mins.removeLast()
    }

    fun top(): Int = data.last()

    fun getMin(): Int = mins.last()
}

• 所有操作 O(1)，空间 O(n)。

非最优解：每次遍历求最小。只用一个栈，getMin 时遍历整个栈找最小值。空间省了，但 getMin 退化到 O(n)，不满足题目”O(1) 取最小”的要求。（进阶：还可用”只存差值”的技巧把辅助栈省掉，可作为加分回答。）

3. 每日温度（中等）

给定每日温度数组，返回一个数组，第 i 项表示第 i 天之后还要等几天才会遇到更高温度，没有则为 0。这是单调栈的典型题。

最优解：单调栈。栈里存”还没等到更高温度的天的下标”，保持栈内对应温度单调递减。遇到更高温度时，把栈里所有比它低的天依次弹出并计算天数差。

/**
 * 每日温度：求每天还要等多少天才有更高温度（单调栈）。
 * Daily temperatures via a monotonic stack.
 * @param temperatures 每日温度数组
 * @return IntArray 每天需要等待的天数
 */
fun dailyTemperatures(temperatures: IntArray): IntArray {
    val res = IntArray(temperatures.size)
    val stack = ArrayDeque<Int>()  // 存下标，对应温度单调递减
    for (i in temperatures.indices) {
        // 当前温度比栈顶那天高，就找到了栈顶那天的答案
        while (stack.isNotEmpty() && temperatures[i] > temperatures[stack.last()]) {
            val prev = stack.removeLast()
            res[prev] = i - prev
        }
        stack.addLast(i)
    }
    return res
}

• 时间 O(n)（每个下标最多进栈出栈一次），空间 O(n)。

非最优解：暴力双重循环。对每一天，往后逐天找第一个更高温度，O(n²)。单调栈的妙处在于”用一个递减栈把已经遍历过、还在等更高温度的天缓存起来”，避免重复回溯，把 O(n²) 降到 O(n)。

4. 逆波兰表达式求值（中等）

计算逆波兰（后缀）表达式的值，如 ["2","1","+","3","*"] = (2+1)*3 = 9。

最优解：栈。遇到数字入栈，遇到运算符弹出栈顶两个数运算后把结果压回。后缀表达式天生适合用栈求值，无需处理运算符优先级。

/**
 * 逆波兰表达式求值。
 * Evaluate reverse Polish notation.
 * @param tokens 逆波兰表达式的 token 数组
 * @return Int 表达式的计算结果
 */
fun evalRPN(tokens: Array<String>): Int {
    val stack = ArrayDeque<Int>()
    for (t in tokens) {
        when (t) {
            "+", "-", "*", "/" -> {
                val b = stack.removeLast()   // 注意：后弹出的是左操作数
                val a = stack.removeLast()
                stack.addLast(
                    when (t) {
                        "+" -> a + b
                        "-" -> a - b
                        "*" -> a * b
                        else -> a / b
                    }
                )
            }
            else -> stack.addLast(t.toInt())  // 数字直接入栈
        }
    }
    return stack.last()
}

• 时间 O(n)，空间 O(n)。

说明：本题栈解法就是标准最优解，几乎没有更差的常见解法可比——它正是”栈解决就近匹配”这一思想的直接体现。面试时要点明减法、除法的操作数顺序（先弹出的是右操作数），这是最容易写错的地方。

二、队列

队列的高频考点是用两个栈模拟队列（考察对两种结构的理解），以及单调队列（滑动窗口极值）。

1. 用两个栈实现队列（简单）

用两个栈实现一个队列，支持在队尾插入、从队首删除。

最优解：一个”入队栈” + 一个”出队栈”。入队都压进 inStack；出队时若 outStack 为空，把 inStack 全部倒进 outStack（顺序恰好反转成 FIFO），再从 outStack 弹出。

/**
 * 用两个栈实现队列。
 * Implement a queue using two stacks.
 */
class MyQueue {
    private val inStack = ArrayDeque<Int>()   // 负责入队
    private val outStack = ArrayDeque<Int>()  // 负责出队

    fun push(x: Int) = inStack.addLast(x)

    fun pop(): Int {
        transfer()
        return outStack.removeLast()
    }

    fun peek(): Int {
        transfer()
        return outStack.last()
    }

    fun empty(): Boolean = inStack.isEmpty() && outStack.isEmpty()

    /**
     * 当出队栈为空时，把入队栈的元素全部倒过去（顺序反转成 FIFO）。
     * Move all elements from inStack to outStack when outStack is empty.
     */
    private fun transfer() {
        if (outStack.isEmpty()) {
            while (inStack.isNotEmpty()) outStack.addLast(inStack.removeLast())
        }
    }
}

• 均摊 O(1)：每个元素最多被”倒”一次，push/pop 均摊常数时间。

非最优解：每次出队都倒来倒去。出队时无脑把元素倒过去、弹出、再倒回来，每次 O(n)。关键优化是”只有 outStack 空了才倒“，让每个元素一生只搬一次，从而做到均摊 O(1)。

2. 滑动窗口最大值（中等偏难）

给定数组和窗口大小 k，窗口从左向右滑动，返回每个窗口内的最大值。这是单调队列的经典题。

最优解：单调队列（双端队列）。队列里存下标，保持对应值单调递减，队首始终是当前窗口的最大值。新元素入队前，把队尾所有比它小的都弹掉；同时把滑出窗口的队首下标移除。

/**
 * 滑动窗口最大值（单调队列）。
 * Sliding window maximum via a monotonic deque.
 * @param nums 整型数组
 * @param k 窗口大小
 * @return IntArray 每个窗口的最大值
 */
fun maxSlidingWindow(nums: IntArray, k: Int): IntArray {
    val res = IntArray(nums.size - k + 1)
    val deque = ArrayDeque<Int>()  // 存下标，对应值单调递减，队首为最大值
    for (i in nums.indices) {
        // 队尾比当前值小的都弹掉（它们不可能再成为最大值）
        while (deque.isNotEmpty() && nums[deque.last()] < nums[i]) deque.removeLast()
        deque.addLast(i)
        // 队首下标已滑出窗口，移除
        if (deque.first() <= i - k) deque.removeFirst()
        // 窗口形成后记录队首（最大值）
        if (i >= k - 1) res[i - k + 1] = nums[deque.first()]
    }
    return res
}

• 时间 O(n)（每个下标最多进出队一次），空间 O(k)。

非最优解一：暴力。对每个窗口遍历求最大值，O(n·k)，数据大时超时。

非最优解二：大顶堆。用堆维护窗口内元素，取堆顶为最大值，O(n log k)。比暴力好，但需要处理”过期元素”（懒删除），且不如单调队列的 O(n)。单调队列的核心思想是”一个新来的大元素，会让它前面所有更小的元素永远失去成为最大值的资格“，所以可以直接把它们丢弃。

三、字符串

字符串题的高频武器是双指针和滑动窗口。很多”最长/最短子串”问题都能用滑动窗口在 O(n) 内解决。

1. 最长公共前缀（简单）

查找字符串数组中所有字符串的最长公共前缀，不存在返回 ""。

最优解：纵向扫描。以第一个字符串为基准，逐列比较所有字符串在该位置的字符，一旦发现不一致或某字符串已到末尾，就返回。

/**
 * 查找字符串数组的最长公共前缀（纵向扫描）。
 * Find the longest common prefix among strings.
 * @param strs 字符串数组
 * @return String 最长公共前缀
 */
fun longestCommonPrefix(strs: Array<String>): String {
    if (strs.isEmpty()) return ""
    // 逐个字符列比较
    for (i in strs[0].indices) {
        val c = strs[0][i]
        for (str in strs) {
            // 某字符串到头了，或字符不一致，公共前缀到此为止
            if (i == str.length || str[i] != c) return strs[0].substring(0, i)
        }
    }
    return strs[0]
}

• 时间 O(n·m)（n 个字符串，m 为最短串长度），空间 O(1)。

非最优解：横向扫描。先算前两个字符串的公共前缀，再拿它和第三个求公共前缀……逐个缩小。复杂度相同，但当数组里有个别很长的公共前缀、后面却出现短的不匹配串时，纵向扫描能更早终止，通常更优。

2. 无重复字符的最长子串（中等）

找出字符串中不含重复字符的最长子串的长度，如 "abcabcbb" 的答案是 3（"abc"）。

最优解：滑动窗口 + 哈希表。右指针不断扩张窗口，用哈希表记录每个字符最近出现的位置；一旦遇到窗口内已存在的重复字符，就把左指针跳到该重复字符上次位置的下一位。

/**
 * 无重复字符的最长子串长度（滑动窗口）。
 * Length of the longest substring without repeating characters.
 * @param s 输入字符串
 * @return Int 最长无重复子串的长度
 */
fun lengthOfLongestSubstring(s: String): Int {
    val lastIndex = HashMap<Char, Int>()  // 字符 -> 最近一次出现的下标
    var left = 0
    var best = 0
    for (right in s.indices) {
        val c = s[right]
        // 若字符在窗口内出现过，左边界跳到其上次位置的下一位
        if (lastIndex.containsKey(c) && lastIndex[c]!! >= left) {
            left = lastIndex[c]!! + 1
        }
        lastIndex[c] = right
        best = maxOf(best, right - left + 1)
    }
    return best
}

• 时间 O(n)，空间 O(min(n, 字符集大小))。

非最优解：暴力枚举所有子串。枚举每个起点，向后延伸直到出现重复，O(n²) 甚至 O(n³)（若每次用 Set 重新判重）。滑动窗口的关键是”左指针只前进不后退“，把两层循环压成一次遍历。

3. 最长回文子串（中等）

找出字符串中最长的回文子串，如 "babad" 的答案是 "bab" 或 "aba"。

最优解：中心扩展。回文串关于中心对称，所以枚举每个可能的中心（n 个单字符中心 + n-1 个字符间隙中心），向两边扩展找最长回文。

/**
 * 最长回文子串（中心扩展法）。
 * Longest palindromic substring by expanding around centers.
 * @param s 输入字符串
 * @return String 最长回文子串
 */
fun longestPalindrome(s: String): String {
    if (s.length < 2) return s
    var start = 0
    var maxLen = 1

    /**
     * 从中心 (l, r) 向两边扩展，返回该中心能得到的最长回文长度。
     * Expand around center (l, r) and return the longest palindrome length.
     */
    fun expand(l: Int, r: Int) {
        var left = l
        var right = r
        while (left >= 0 && right < s.length && s[left] == s[right]) {
            left--
            right++
        }
        // 循环结束时多走了一步，真实长度为 right - left - 1
        val len = right - left - 1
        if (len > maxLen) {
            maxLen = len
            start = left + 1
        }
    }

    for (i in s.indices) {
        expand(i, i)      // 奇数长度回文，中心是单个字符
        expand(i, i + 1)  // 偶数长度回文，中心是两个字符间隙
    }
    return s.substring(start, start + maxLen)
}

• 时间 O(n²)，空间 O(1)。

非最优解一：暴力。枚举所有子串再逐个判断是否回文，O(n³)。

非最优解二：动态规划。dp[i][j] 表示 s[i..j] 是否回文，dp[i][j] = (s[i]==s[j]) && dp[i+1][j-1]。时间 O(n²) 但空间也要 O(n²)，不如中心扩展省空间。（追求极致可用 O(n) 的 Manacher 算法，但实现复杂，面试能讲清中心扩展即可。）

4. 字符串相加（简单）

给定两个用字符串表示的非负整数 num1、num2，返回它们的和（字符串形式），不能直接转成整数（大数会溢出）。牛客高频题。

最优解：双指针从末位模拟竖式加法。两个指针从两字符串末尾开始，逐位相加并处理进位，结果逆序拼接。

/**
 * 字符串形式的大数相加。
 * Add two non-negative integers represented as strings.
 * @param num1 第一个数字字符串
 * @param num2 第二个数字字符串
 * @return String 两数之和的字符串
 */
fun addStrings(num1: String, num2: String): String {
    val sb = StringBuilder()
    var i = num1.length - 1
    var j = num2.length - 1
    var carry = 0  // 进位
    while (i >= 0 || j >= 0 || carry > 0) {
        val a = if (i >= 0) num1[i--] - '0' else 0
        val b = if (j >= 0) num2[j--] - '0' else 0
        val sum = a + b + carry
        sb.append(sum % 10)   // 当前位
        carry = sum / 10      // 进位
    }
    return sb.reverse().toString()
}

• 时间 O(max(m, n))，空间 O(max(m, n))（结果）。

非最优解：转成整数相加。(num1.toLong() + num2.toLong()).toString()。看似简单，但大数会溢出（题目正是要考这个），只能用于长度很小的输入，是本题明确要避开的错误解法。

结语：三种结构的”套路武器”

结构	高频武器	一句话心法
栈	单调栈	“找下一个更大/更小元素”就用它，把 O(n²) 降到 O(n)
队列	单调队列、双栈	滑动窗口极值用单调队列；两个栈可互相模拟另一种结构
字符串	双指针、滑动窗口	“最长/最短无重复子串”优先想滑动窗口，左指针只进不退

💡 面试建议：单调栈和单调队列是很多人的盲区，但它们的思想其实一致——及时丢弃那些”永远不可能再成为答案”的元素（被更大的数挡住、或已滑出窗口）。想清楚”什么样的元素可以安全丢弃”，这两类题就通了。更基础的数组/链表/哈希/二叉树题，见上一篇 高频算法面试题整理。