LeetCode刷题 | Day 2 最长严格递增或递减子列表（Longest Increasing Decreasing SubList）
<hr>
<hr> 前言
LeetCode位置：3105. 最长的严格递增或递减子数组
一样平常刷题，维持手感，同步学习英语，刷题顺序参考B站UP@justyyuk的系列视频，感兴趣的点波关注。
学海无涯，大路千万，感恩此程，彼此朴拙陪伴！
Ps：第一次刷到的道友留步，这里拉齐一下信息。文章主要记录视频中的主要内容，算法思路会按照个人理解，用伪代码+举例每步输出的方式呈现。代码部门会以Python和C++语法进行呈现。文章末了会总结一些英语词汇。OK，就啰嗦这么多，开始进步[干杯]
<hr> 一、题目概述
本题与UP主justyyuk的题目差异（UP主题目：最长严格递增然后递减子列表），但解题思路类似（末了一步差异），故这里以LeetCode为主。
输入：nums列表
输出：最长严格递增然后递减子列表长度
PS：
- 子序列 (Subsequence):
- 子序列是通过从原始序列中删除一些或不删除任何元素且不改变剩余元素顺序而得到的序列。
- 例子：对于序列 [1, 2, 3, 4]，[1, 3, 4] 和 [2, 4] 是子序列。
- 留意：[1, 4, 3] 不是 子序列，因为顺序改变了。
- 子列表 (Sublist)
- 子列表是列表的连续部门，意味着元素必须是连续的。
- 例子：对于列表 [1, 2, 3, 4]，[2, 3] 和 [1, 2, 3]是子列表。
- 留意：[1, 3] 不是 子列表，因为它不是连续的。
- 子数组 (Subarray):
- 类似于子列表，子数组是数组的连续部门。
- 例子：对于数组 [1, 2, 3, 4]，[2, 3] 和 [1, 2, 3] 是子数组。
- 留意：[1, 3] 不是 子数组，因为它不是连续的。
- 在很多情况下，当数据布局是数组或列表时，“子列表”和“子数组”可以交换使用，但“子数组”一词专门用于数组。
二、解题方法
2.1 动态规划头脑
2.1.1 思路讲解
Ps： 动态规划（Dynamic Programming）特征
- 最优子布局：
- 动态规划要求问题具有最优子布局性质，即问题的最优解包罗其子问题的最优解。
- 重叠子问题：
- 动态规划必要问题具有重叠子问题性质，即差异的子问题在求解时会重复出现。
- 状态转移方程：
- 动态规划通过状态转移方程将问题分解为子问题，并通过子问题的解来推导原问题的解。
- 全局最优解：
- 动态规划通过观察全部可能的子问题组合来确保找到全局最优解。
- 影象化或表格法：
- 动态规划通常使用影象化搜索或自底向上的表格法来避免重复计算。
- 动态规划策略
- 分别计算数组中每个位置的单调递增和单调递减子数组的长度，终极得到最长单调子数组的长度。
- 详细步调
- 使用两个数组 inc 和 dec，分别存储每个位置上最长单调递增和单调递减子数组的长度，初始值均为 1。
- 从前去后遍历 nums 数组，若当前元素大于前一个元素，则当前位置的递增长度等于前一个位置的递增长度加一。
- 从后往前遍历 nums 数组，若当前元素大于后一个元素，则当前位置的递减长度等于后一个位置的递减长度加一。
- 终极结果为 inc 和 dec 两个数组中的最大值，即最长的单调子数组长度。
2.1.2 伪代码 + 徐徐输出示例
- # 伪代码示例
- 函数 longestMonotonicSubarray(nums):
- n = nums 的长度
- 初始化 inc 数组为 [1] * n
- 初始化 dec 数组为 [1] * n
-
- 对于 i 从 1 到 n-1:
- 如果 nums[i] > nums[i-1]:
- inc[i] = inc[i-1] + 1
- 对于 i 从 n-2 到 0:
- 如果 nums[i] > nums[i+1]:
- dec[i] = dec[i+1] + 1
-
- ans = inc 和 dec 数组中的最大值
- 返回 ans
- # 逐步输出示例
- 输入: nums = [1, 2, 2, 3, 2, 1, 4]
- 步骤:
- 1. n = 7
- 2. 初始化 inc 数组为 [1, 1, 1, 1, 1, 1, 1]
- 3. 初始化 dec 数组为 [1, 1, 1, 1, 1, 1, 1]
- 4. 第一个 for 循环 (计算递增子数组长度):
- i = 1, nums[1] (2) > nums[0
|
