算法题：最长有效括号与股票交易

§面试白板流程

白板算法题考核的是「沟通中解题」的过程，而非默写最优解；一套固定的作答流程能保证每一步都产生可被面试官评分的信号。

Q14最长有效括号（LeetCode 32 · Hard）

题意与例子

给定只含 '(' 与 ')' 的字符串，求最长的格式正确且连续的括号子串长度。两个关键词都参与判定：「格式正确」意味着每个右括号都有匹配的左括号；「连续」意味着求的是子串而非子序列。

• "(()" → 答案 2（最长有效子串为 "()"）
• ")()())" → 答案 4（最长有效子串为 "()()"，下标 1–4）
• "" → 答案 0

暴力基线：枚举所有子串并用栈验证合法性，O(n³)；只枚举起点、扫描中维护计数器可降到 O(n²)。报完基线复杂度后引出线性解法。

解法一：栈（主推）

思路：栈中存下标而非字符，核心不变量是——栈底永远是「最后一个未匹配位置」。初始压入哨兵 -1，使该不变量从第 0 个字符起就成立。遇 '(' 压入其下标；遇 ')' 先 pop：若 pop 后栈空，说明这个右括号无法匹配，把当前下标压入作为新基准；否则当前位置到新栈顶之间的整段都有效，更新 ans = max(ans, i - stack[-1])。

def longestValidParentheses(s: str) -> int:
    stack = [-1]
    ans = 0
    for i, ch in enumerate(s):
        if ch == '(':
            stack.append(i)
        else:
            stack.pop()
            if not stack:
                stack.append(i)
            else:
                ans = max(ans, i - stack[-1])
    return ans

L2哨兵 -1 统一了「上一个未匹配位置」的语义　L9-10栈空说明右括号过剩，当前下标成为新基准　L12有效长度 = 当前下标 − 栈顶下标

复杂度：每个下标至多入栈、出栈各一次，时间 O(n)，空间 O(n)。

逐步走例子 ")()())"：

最终返回 4，与最长有效子串 "()()"（下标 1–4）一致。

解法二：动态规划

思路：定义 dp[i] 为「以下标 i 结尾的最长有效括号长度」。s[i] == '(' 时 dp[i] = 0（左括号结尾不构成有效串）；s[i] == ')' 时分两种情形：

• s[i-1] == '('，即形如 "…()"：dp[i] = dp[i-2] + 2；
• s[i-1] == ')' 且 s[i - dp[i-1] - 1] == '('，即形如 "…((…))"：跳过中间已匹配的 dp[i-1] 段，与外层左括号配对，再拼接外层左括号之前的有效段——dp[i] = dp[i-1] + 2 + dp[i - dp[i-1] - 2]。

两条转移中下标越界的项按 0 处理。

def longestValidParentheses(s: str) -> int:
    n = len(s)
    dp = [0] * n
    ans = 0
    for i in range(1, n):
        if s[i] == ')':
            if s[i-1] == '(':
                dp[i] = (dp[i-2] if i >= 2 else 0) + 2
            elif i - dp[i-1] - 1 >= 0 and s[i - dp[i-1] - 1] == '(':
                dp[i] = dp[i-1] + 2 + (dp[i - dp[i-1] - 2] if i - dp[i-1] - 2 >= 0 else 0)
            ans = max(ans, dp[i])
    return ans

复杂度：时间 O(n)，空间 O(n)。与栈法同阶，但状态定义「以 i 结尾」是区间型 DP 的通用套路，值得在白板上点明。

解法三：双向计数（O(1) 空间）

思路：维护 left/right 两个计数器。从左向右扫：遇 '(' 加 left，遇 ')' 加 right；left == right 时出现一段有效串，更新 ans = 2 * right；right > left 时该前缀已不合法，两计数器清零。这一遍会漏掉 left > right 的情形（如 "(()"，left 始终领先，永远等不到相等），因此再从右向左对称扫一遍：角色互换，left > right 时清零。

def longestValidParentheses(s: str) -> int:
    ans = 0
    left = right = 0
    for ch in s:                  # 左 → 右
        if ch == '(':
            left += 1
        else:
            right += 1
        if left == right:
            ans = max(ans, 2 * right)
        elif right > left:
            left = right = 0
    left = right = 0
    for ch in reversed(s):        # 右 → 左
        if ch == ')':
            right += 1
        else:
            left += 1
        if left == right:
            ans = max(ans, 2 * left)
        elif left > right:
            left = right = 0
    return ans

复杂度：时间 O(n)，空间 O(1)。当面试官追问「空间还能不能再省」时，这是栈法之后的标准升级答案。

加分点

• 说清第二遍反向扫描的必要性：正向扫描只在 left == right 时结算，"(()" 这类左括号过剩的前缀永远满足 left > right，正扫不会触发结算也不会清零，长度被漏报；反向扫描以右括号视角对称处理，恰好补上这一半情形。
• 说清栈底哨兵 −1 的作用：它把「上一个未匹配位置」的语义统一到栈底，使 i - stack[-1] 在任何时刻都直接给出以 i 结尾的有效长度，省去对空栈的特判分支。
• 主动对比三个解法：栈法语义最直观、DP 展示状态设计能力、双向计数赢在空间——选「主推栈法、口述另两条路线」的策略本身就是工程判断力的展示。

追问预判

Q15股票交易（LeetCode 买卖股票系列）

第一步：澄清变体

「股票交易」是一个题族，约束不同解法完全不同。面试官说出题面后，正确的第一反应是反问：「允许交易几次？有冷冻期或手续费吗？」这表明候选人理解需求边界先于编码——与系统设计题的第一步完全一致。

面试中通常按前两个主变体作答，再用统一框架收束全族。

变体一：LC121，仅一次交易

思路：一次遍历，维护两个量——到当前为止的历史最低价 min_price，以及「今天卖出」能得到的最大利润。每天先用今日价格刷新最低价，再用「今日价 − 历史最低价」刷新答案。

def maxProfit(prices: list[int]) -> int:
    min_price = float('inf')
    ans = 0
    for p in prices:
        min_price = min(min_price, p)
        ans = max(ans, p - min_price)
    return ans

复杂度：时间 O(n)，空间 O(1)。单调下跌的行情下答案为 0（不交易），代码无需特判即覆盖。

变体二：LC122，不限次数

思路：贪心收集所有正向日差——sum(max(0, prices[i] - prices[i-1]))，等价于把所有上升段全部吃下。任何交易区间的利润都等于区间内相邻日差之和，删去负项不降低收益，因此正项之和既是上界又是可达方案。

def maxProfit(prices: list[int]) -> int:
    return sum(max(0, prices[i] - prices[i-1])
               for i in range(1, len(prices)))

复杂度：时间 O(n)，空间 O(1)。

统一框架：状态机 DP（强加分）

整个题族共享一个状态机：每天处于两个状态之一——hold（持股）与 empty（空仓），变量值为该状态下的最大利润。每天的价格 p 触发状态转移：

• hold = max(hold, empty - p)：继续持股，或今天买入；
• empty = max(empty, hold + p)：继续空仓，或今天卖出。

初始值 hold = -inf（第 0 天之前不存在持股状态，−inf 表示不可达）、empty = 0。遍历结束后答案取 empty——持仓未平不算落袋。

def maxProfit_unlimited(prices: list[int]) -> int:
    hold, empty = float('-inf'), 0
    for p in prices:
        hold = max(hold, empty - p)
        empty = max(empty, hold + p)
    return empty

复杂度：时间 O(n)，空间 O(1)。

这个状态机的扩展能力是它的真正价值：给状态加上「交易次数」维度即统一解 LC123 / LC188；在 empty 与 hold 之间插入 cooldown 状态解 LC309；卖出转移中扣除手续费解 LC714。画成状态转移图，正是 02 章 Agent 架构中 FSM 的「状态 + 事件 + 转移函数」三要素——在白板上点出这一呼应，算法题就接回了系统设计的主线。

加分点

• 先澄清变体再动笔：题面模糊时反问约束，与系统设计题「先问需求边界」同源，面试官在等这个动作。
• 报出题号族谱：LC121 / 122 / 123 / 188 / 309 / 714 是同一状态机在不同约束下的扩展——展示的是体系化认知而非刷题量。
• 贪心正确性的一句话交换论证：任意交易方案的利润可拆为相邻日差之和，把方案中的负差项删去（拆成多段交易）收益不减，所以全部正差之和是最优值。

追问预判