当前位置：首页 > news >正文

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

news 2026/8/11 5:56:22

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"返回3

3. 含冷却期的股票买卖问题

3.1 问题建模

给定一个股票价格数组prices，其中prices[i]表示第i天的股票价格。设计算法计算最大利润，交易规则为：

可以完成任意次交易
卖出股票后需要等待一天才能再次买入（冷却期）
不能同时进行多笔交易（必须卖出当前持有股票后才能再买入）

示例：prices = [1,2,3,0,2] 最大利润为3，对应交易序列：买入1，卖出2（利润1），冷却，买入0，卖出2（利润2）

3.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)。