LeetCode 896题：单调数列的高效解法与优化

1. 单调数列问题解析

今天我们来深入探讨LeetCode第896题"单调数列"的高效解法。这道题看似简单，但想要写出时间复杂度最优的解法，需要仔细分析数组的单调性特征。

单调数列的定义是：数组中的所有元素要么单调递增，要么单调递减。换句话说，对于数组中的任意相邻两个元素，要么满足nums[i] <= nums[i+1]（递增），要么满足nums[i] >= nums[i+1]（递减）。

2. 解法思路分析

2.1 暴力解法的问题

最直观的想法可能是先对数组进行排序，然后比较原数组是否等于排序后的数组（判断是否递增）或逆序后的排序数组（判断是否递减）。这种方法虽然思路简单，但时间复杂度为O(nlogn)，因为排序操作本身就需要O(nlogn)的时间。

// 不推荐的排序解法示例 vector<int> tmp = nums; sort(nums.begin(), nums.end()); // 检查是否递增 bool isIncreasing = true; for(int i=0; i<n; i++) { if(tmp[i] != nums[i]) { isIncreasing = false; break; } } // 检查是否递减 bool isDecreasing = true; for(int i=0; i<n; i++) { if(tmp[n-i-1] != nums[i]) { isDecreasing = false; break; } } return isIncreasing || isDecreasing;

这种解法的问题在于做了很多不必要的计算，特别是当数组很大时，排序操作会成为性能瓶颈。

2.2 高效解法的关键思路

更高效的解法应该只需要遍历数组一次，时间复杂度为O(n)。我们可以通过以下步骤实现：

1. 首先处理特殊情况：数组长度小于等于2时，必定是单调的
2. 跳过所有相等的相邻元素，找到第一个不相等的相邻元素对
3. 根据这对元素确定数组应该是递增还是递减
4. 继续遍历剩余元素，验证是否符合确定的单调性

3. 代码实现详解

3.1 核心代码解析

让我们仔细分析提供的优化解法：

class Solution { public: bool isMonotonic(vector<int>& nums) { int n = nums.size(), k = 1; // 特殊情况处理 if(n <= 2) return true; // 跳过所有相等的相邻元素 while(k < n && nums[k-1] == nums[k]) k++; // 如果全部元素相等 if(k == n) return true; // 确定单调方向 bool increasing = (nums[k-1] < nums[k]); // 验证后续元素是否符合单调性 for(int i = k; i < n; i++) { if(nums[i-1] != nums[i]) { if(increasing != (nums[i-1] < nums[i])) { return false; } } } return true; } };

3.2 关键步骤说明

1. 特殊情况处理：当数组长度≤2时，必定是单调的，直接返回true
2. 跳过相等元素：使用while循环跳过所有相邻的相等元素，因为这些元素不影响单调性判断
3. 确定单调方向：找到第一个不相等的相邻元素对，比较它们的大小确定是递增还是递减
4. 验证单调性：遍历剩余元素，检查每个不相等的相邻元素对是否符合确定的单调方向

3.3 时间复杂度分析

这个解法只需要遍历数组两次：

1. 第一次是跳过相等的相邻元素（最坏情况O(n)）
2. 第二次是验证单调性（O(n)） 因此总时间复杂度是O(n)，比排序解法更高效。

4. 边界条件与测试用例

4.1 常见边界情况

编写算法时需要考虑以下边界情况：

1. 空数组或单元素数组
2. 所有元素相等的数组
3. 严格递增/递减的数组
4. 非严格递增/递减的数组（包含相等元素）
5. 既非递增也非递减的数组

4.2 测试用例示例

// 测试用例 vector<int> test1 = {1,2,2,3}; // 单调递增 vector<int> test2 = {6,5,4,4}; // 单调递减 vector<int> test3 = {1,3,2}; // 非单调 vector<int> test4 = {1,1,1}; // 所有元素相等 vector<int> test5 = {1}; // 单元素

5. 算法优化与变种

5.1 一次遍历的实现

上述解法虽然高效，但理论上可以进一步优化为只遍历数组一次：

bool isMonotonic(vector<int>& nums) { bool increasing = true; bool decreasing = true; for(int i = 1; i < nums.size(); i++) { if(nums[i] > nums[i-1]) decreasing = false; if(nums[i] < nums[i-1]) increasing = false; // 提前终止条件 if(!increasing && !decreasing) return false; } return increasing || decreasing; }

这种实现同时跟踪递增和递减的可能性，一旦两者都为false就可以提前返回结果。

5.2 性能比较

两种优化解法的时间复杂度都是O(n)，但第二种实现：

1. 只需要一次遍历
2. 有提前终止的条件 因此在大多数情况下性能会更好，特别是当数组明显非单调时。

6. 实际应用场景

单调数列的判断在实际开发中有多种应用场景：

1. 数据质量检查：验证时间序列数据是否单调递增（如日志时间戳）
2. 算法预处理：某些算法（如二分查找）要求输入数据是单调的
3. 系统监控：检测指标值是否持续增长或下降（如内存使用量）

7. 常见错误与调试技巧

7.1 常见实现错误

1. 忽略相等元素：没有正确处理相邻相等元素的情况
2. 方向判断错误：在确定单调方向时逻辑错误
3. 边界条件遗漏：没有处理空数组或全等数组的情况

7.2 调试建议

1. 使用小规模测试用例手动验证
2. 打印中间变量（如确定的单调方向）
3. 使用可视化工具观察数组变化趋势

8. 扩展思考

对于更复杂的情况，比如：

1. 判断数组是否是"山峰"或"山谷"形状
2. 找出最长的单调子数组
3. 将非单调数组变为单调所需的最小操作数

这些问题都可以基于单调数列的判断进行扩展，是很好的算法练习题目。

在实际面试中，面试官可能会要求你：

1. 解释算法的时间复杂度
2. 分析空间复杂度（本例是O(1)）
3. 讨论不同解法的优缺点
4. 提出进一步的优化建议

掌握这类基础算法问题的解决思路，对于提升编程能力和面试表现都很有帮助。建议读者可以尝试实现不同的解法，并比较它们的性能差异。