滑动窗口与动态规划：解决无重复子串与股票收益问题

1. 算法实战无重复字符的最长子串与含冷却期的股票最大收益在算法面试和编程竞赛中字符串处理和动态规划是两类经典问题。今天我想分享两个看似不同但都考验思维模式的题目解法找出字符串中最长无重复字符的子串Longest Substring Without Repeating Characters以及带有卖出冷却期的股票买卖最大收益问题Maximum Profit with Cooldown。这两个问题分别来自LeetCode的第3题和第309题在实际面试中出现频率极高。第一个问题考察滑动窗口技巧的应用需要在线性时间内完成字符串扫描第二个问题则需要设计包含状态转移的动态规划方案考虑交易规则的约束条件。虽然领域不同但都体现了算法设计中如何高效处理约束条件的核心思想。下面我会结合代码示例和状态转移图拆解这两个问题的解决思路和优化技巧。2. 无重复字符的最长子串解析2.1 问题定义与暴力解法给定一个字符串s要求找出其中不含有重复字符的最长子串的长度。例如abcabcbb的最长无重复子串是abc长度为3。最直观的暴力解法是检查所有可能的子串def lengthOfLongestSubstring(s): max_len 0 for i in range(len(s)): seen set() for j in range(i, len(s)): if s[j] in seen: break seen.add(s[j]) max_len max(max_len, len(seen)) return max_len这种方法时间复杂度为O(n²)当字符串较长时性能堪忧。2.2 滑动窗口优化方案更高效的方案是使用滑动窗口配合哈希表记录字符位置def lengthOfLongestSubstring(s): char_index {} left max_len 0 for right, char in enumerate(s): if char in char_index and char_index[char] left: left char_index[char] 1 char_index[char] right max_len max(max_len, right - left 1) return max_len这个算法的时间复杂度优化到O(n)空间复杂度O(min(m,n))其中m是字符集大小。关键技巧当发现重复字符时直接将窗口左边界跳到该字符上次出现位置的下一位避免不必要的重复检查。2.3 边界条件与测试用例需要特别注意的边界情况包括空字符串输入() → 应返回0全相同字符(aaaaa) → 应返回1无重复字符(abcdef) → 应返回字符串长度混合情况(pwwkew) → 最长子串wke返回33. 含冷却期的股票买卖问题3.1 问题建模给定一个股票价格数组prices其中prices[i]表示第i天的股票价格。设计算法计算最大利润交易规则为可以完成任意次交易卖出股票后需要等待一天才能再次买入冷却期不能同时进行多笔交易必须卖出当前持有股票后才能再买入示例prices [1,2,3,0,2] 最大利润为3对应交易序列买入1卖出2利润1冷却买入0卖出2利润23.2 动态规划状态设计定义三个状态hold[i]第i天结束时持有股票的最大利润sold[i]第i天结束时不持有股票且处于冷却期的最大利润rest[i]第i天结束时不持有股票且不处于冷却期的最大利润状态转移方程hold[i] max(hold[i-1], rest[i-1] - prices[i]) sold[i] hold[i-1] prices[i] rest[i] max(rest[i-1], sold[i-1])最终结果为max(sold[n-1], rest[n-1])3.3 Python实现与空间优化def maxProfit(prices): if not prices: return 0 hold -prices[0] sold 0 rest 0 for i in range(1, len(prices)): prev_hold hold hold max(hold, rest - prices[i]) rest max(rest, sold) sold prev_hold prices[i] return max(sold, rest)通过变量复用将空间复杂度从O(n)优化到O(1)。4. 算法对比与经验总结4.1 解题模式差异滑动窗口适用于子串/子数组类问题通过维护窗口边界来避免重复计算状态机DP适用于带约束条件的序列决策问题通过明确定义状态来理清转移逻辑4.2 常见错误排查对于无重复子串问题忘记更新字符最后出现位置窗口左边界移动时未考虑历史位置对于股票问题混淆hold和rest状态的转移条件初始化时未正确处理base case冷却期状态转移遗漏前一天卖出操作4.3 性能优化技巧滑动窗口问题可以先用暴力解法验证逻辑正确性动态规划问题建议先画出状态转移图对于空间敏感的场景观察是否只需要前一个状态使用断言(assert)验证边界条件在实际面试中建议先明确问题约束条件再选择合适的数据结构和算法范式。这两个问题虽然领域不同但都体现了算法设计中对问题约束条件的建模能力。