从‘最长平台’到‘最大连续子数组’：用动态规划打通算法思路（以洛谷B2097为例）

从‘最长平台’到动态规划：用算法思维拆解序列问题

在算法学习的道路上，很多初学者都会遇到一个共同的困惑：为什么看似简单的问题却需要复杂的解法？比如计算一个序列中连续相同元素的最大长度（即"最长平台"问题），表面上看只需要遍历统计，但深入思考会发现它蕴含着动态规划、双指针等核心算法思想。本文将以洛谷B2097题为例，带你从多个维度重新审视这个"简单"问题，并揭示其与经典算法问题的深层联系。

1. 问题本质与暴力解法

最长平台问题的描述非常简单：给定一个整数序列，找出其中最长的连续相同数字子序列的长度。比如序列[1,2,2,3,3,3,2]的最长平台是3，因为数字3连续出现了3次。

1.1 直观解法分析

最直接的思路是遍历数组，同时维护几个关键变量：

• lastNum：记录上一个数字
• currentLen：当前平台的连续长度
• maxLen：已发现的最大平台长度

int findMaxPlatform(vector<int>& nums) { if(nums.empty()) return 0; int lastNum = nums[0], currentLen = 1, maxLen = 1; for(int i = 1; i < nums.size(); i++) { if(nums[i] == lastNum) { currentLen++; maxLen = max(maxLen, currentLen); } else { lastNum = nums[i]; currentLen = 1; } } return maxLen; }

这种解法的时间复杂度是O(n)，空间复杂度是O(1)，已经相当高效。但如果我们止步于此，就错过了深入理解算法设计的机会。

1.2 解法的局限性思考

虽然上述解法能正确解决问题，但它存在几个值得思考的局限：

1. 无法记录多个平台信息：只能得到最大长度，无法知道哪些数字形成了这个平台
2. 难以扩展：如果问题变为"求所有平台长度的平均值"或"找出长度大于k的平台"，代码结构需要大幅修改
3. 缺乏通用性：这种特殊解法难以迁移到其他类似问题上

提示：优秀的算法设计应该考虑可扩展性和通用性，这正是我们需要探索更优解法的原因。

2. 双指针技术的应用

双指针（Two Pointers）是处理序列问题的强大技术，让我们看看如何用它解决最长平台问题。

2.1 双指针解法实现

int findMaxPlatform(vector<int>& nums) { if(nums.empty()) return 0; int maxLen = 1; for(int left = 0; left < nums.size(); ) { int right = left; while(right < nums.size() && nums[right] == nums[left]) { right++; } maxLen = max(maxLen, right - left); left = right; } return maxLen; }

2.2 双指针解法的优势

这种解法相比暴力方法有几个显著优点：

2.3 双指针技术的通用性

双指针技术不仅适用于最长平台问题，还能解决许多类似问题：

• 有序数组的两数之和
• 移除排序数组中的重复项
• 盛最多水的容器问题
• 最小覆盖子串问题

理解这一点后，你就掌握了一个解决序列问题的通用工具，而不仅限于特定题目。

3. 动态规划视角解析

动态规划（DP）是算法设计的核心思想之一，让我们从DP的角度重新审视最长平台问题。

3.1 状态定义与转移方程

定义dp[i]表示以第i个元素结尾的最长平台长度。状态转移方程为：

dp[i] = { dp[i-1] + 1, 如果 nums[i] == nums[i-1] 1, 否则 }

初始条件：dp[0] = 1

3.2 DP解法实现

int findMaxPlatform(vector<int>& nums) { if(nums.empty()) return 0; vector<int> dp(nums.size(), 1); int maxLen = 1; for(int i = 1; i < nums.size(); i++) { if(nums[i] == nums[i-1]) { dp[i] = dp[i-1] + 1; maxLen = max(maxLen, dp[i]); } } return maxLen; }

3.3 DP解法的空间优化

注意到dp[i]只依赖于dp[i-1]，可以进行空间优化：

int findMaxPlatform(vector<int>& nums) { if(nums.empty()) return 0; int prev = 1, maxLen = 1; for(int i = 1; i < nums.size(); i++) { int current = (nums[i] == nums[i-1]) ? prev + 1 : 1; maxLen = max(maxLen, current); prev = current; } return maxLen; }

3.4 DP思想的通用性

这种DP思路可以推广到许多类似问题：

• 最大子数组和（Kadane算法）
• 最长递增子序列
• 最长公共子序列
• 股票买卖最佳时机问题

理解这种状态定义和转移方程的构建方式，是掌握动态规划的关键。

4. 算法思维进阶：问题变体与扩展

掌握了基础解法后，让我们思考几个问题变体，以深化算法理解。

4.1 变体一：找出所有最长平台

不仅要找出最长平台的长度，还要找出所有达到这个长度的数字。

vector<int> findAllMaxPlatforms(vector<int>& nums) { vector<int> result; if(nums.empty()) return result; int currentLen = 1, maxLen = 1; for(int i = 1; i < nums.size(); i++) { if(nums[i] == nums[i-1]) { currentLen++; if(currentLen > maxLen) { maxLen = currentLen; result.clear(); result.push_back(nums[i]); } else if(currentLen == maxLen) { result.push_back(nums[i]); } } else { currentLen = 1; if(maxLen == 1) { result.push_back(nums[i]); } } } // 处理第一个元素 if(maxLen == 1 && find(result.begin(), result.end(), nums[0]) == result.end()) { result.push_back(nums[0]); } return result; }

4.2 变体二：二维平台问题

考虑二维矩阵中的最长平台：在m×n矩阵中找出行或列方向上的最长连续相同元素序列。

int findMaxPlatform2D(vector<vector<int>>& matrix) { if(matrix.empty() || matrix[0].empty()) return 0; int m = matrix.size(), n = matrix[0].size(); int maxLen = 1; // 检查行方向 for(int i = 0; i < m; i++) { int currentLen = 1; for(int j = 1; j < n; j++) { if(matrix[i][j] == matrix[i][j-1]) { currentLen++; maxLen = max(maxLen, currentLen); } else { currentLen = 1; } } } // 检查列方向 for(int j = 0; j < n; j++) { int currentLen = 1; for(int i = 1; i < m; i++) { if(matrix[i][j] == matrix[i-1][j]) { currentLen++; maxLen = max(maxLen, currentLen); } else { currentLen = 1; } } } return maxLen; }

4.3 变体三：带限制的平台问题

找出满足特定条件的最长平台，比如平台中的数字必须大于某个阈值。

int findMaxPlatformWithThreshold(vector<int>& nums, int threshold) { if(nums.empty()) return 0; int currentLen = 0, maxLen = 0; for(int num : nums) { if(num > threshold) { currentLen++; maxLen = max(maxLen, currentLen); } else { currentLen = 0; } } return maxLen; }

5. 从具体问题到通用算法思维

最长平台问题虽然简单，但它体现了算法设计的几个核心思想：

5.1 问题分解与抽象

将具体问题抽象为通用模型是算法设计的关键步骤。最长平台问题可以抽象为：

• 序列中的连续相同元素段识别
• 极值统计问题
• 状态转移问题

5.2 算法选择与优化

针对同一问题，不同算法有不同特性：

5.3 知识迁移与应用

理解最长平台问题的解法后，可以将其应用到更复杂的问题中：

• DNA序列分析中的重复片段检测
• 时间序列数据中的稳定期识别
• 图像处理中的连续区域检测

在实际编程竞赛中，我经常发现许多复杂问题本质上都是简单问题的组合或扩展。比如有一次遇到一个关于游戏地图区域划分的问题，核心就是二维平台问题的变体，通过将问题分解识别，最终用类似双指针的方法高效解决了。