更新题解列表

itcharge · itcharge · commit 5317114d0237 · 2024-01-02T14:48:00.000+08:00
diff --git a/Solutions/0334. 递增的三元子序列.md b/Solutions/0334. 递增的三元子序列.md
@@ -9,35 +9,60 @@
 
 ## 题目大意
 
-给定一个整数数组 `nums`。
+**描述**：给定一个整数数组 $nums$。
 
-要求：判断数组中是否存在长度为 3 的递增子序列。要求算法时间复杂度为 $O(n)$、空间复杂度为 $O(1)$。
+**要求**：判断数组中是否存在长度为 3 的递增子序列。
 
-- 长度为 3 的递增子序列：存在这样的三元组下标 (`i`, `j`, `k`) 且满足 `i < j < k` ，使得 `nums[i] < nums[j] < nums[k]`。
+**说明**：
+
+- 要求算法时间复杂度为 $O(n)$、空间复杂度为 $O(1)$。
+- **长度为 $3$ 的递增子序列**：存在这样的三元组下标 ($i$, $j$, $k$) 且满足 $i < j < k$ ，使得 $nums[i] < nums[j] < nums[k]$。
+- $1 \le nums.length \le 5 \times 10^5$。
+- $-2^{31} \le nums[i] \le 2^{31} - 1$。
+
+**示例**：
+
+- 示例 1：
+
+```python
+输入：nums = [1,2,3,4,5]
+输出：true
+解释：任何 i < j < k 的三元组都满足题意
+```
+
+- 示例 2：
+
+```python
+输入：nums = [5,4,3,2,1]
+输出：false
+解释：不存在满足题意的三元组
+```
 
 ## 解题思路
 
+### 思路 1：快慢指针
+
 常规方法是三重 `for` 循环遍历三个数，但是时间复杂度为 $O(n^3)$，肯定会超时的。
 
 那么如何才能只进行一次遍历，就找到长度为 3 的递增子序列呢？
 
-假设长度为 3 的递增子序列元素为 `a`、`b`、`c`，`a < b < c`。
+假设长度为 3 的递增子序列元素为 $a$、$b$、$c$，$a < b < c$。
 
-先来考虑 `a` 和 `b`。如果我们要使得一个数组  `i < j`，并且 `nums[i] < nums[j]`。那么应该使得 `a` 尽可能的小，这样子我们下一个数字 `b` 才可以尽可能地满足条件。
+先来考虑 $a$ 和 $b$。如果我们要使得一个数组  $i < j$，并且 $nums[i] < nums[j]$。那么应该使得 $a$ 尽可能的小，这样子我们下一个数字 $b$ 才可以尽可能地满足条件。
 
-同样对于 `b` 和 `c`，也应该使得 `b` 尽可能的小，下一个数字 `c` 才可以尽可能的满足条件。
+同样对于 $b$ 和 $c$，也应该使得 $b$ 尽可能的小，下一个数字 $c$ 才可以尽可能的满足条件。
 
-所以，我们的目的是：在 `a < b` 的前提下，保证 a 尽可能小。在 `b < c` 的条件下，保证 `b` 尽可能小。
+所以，我们的目的是：在 $a < b$ 的前提下，保证 a 尽可能小。在 $b < c$ 的条件下，保证 $b$ 尽可能小。
 
-我们可以使用两个数 `a`、`b` 指向无穷大。遍历数组：
+我们可以使用两个数 $a$、$b$ 指向无穷大。遍历数组：
 
-- 如果当前数字小于等于 `a` ，则更新 `a = num`；
-- 如果当前数字大于等于 `a`，则说明当前数满足 `num > a`，则判断：
-  - 如果 `num` 小于等于 `b`，则更新 `b = num`；
-  - 如果 `num` 大于 `b`，则说明找到了长度为 3 的递增子序列，直接输出 `True`。
-- 如果遍历完仍未找到，则输出 `False`。
+- 如果当前数字小于等于 $a$ ，则更新 `a = num`；
+- 如果当前数字大于等于 $a$，则说明当前数满足 $num > a$，则判断：
+  - 如果 $num \le b$，则更新 `b = num`；
+  - 如果 $num > b$，则说明找到了长度为 3 的递增子序列，直接输出 $True$。
+- 如果遍历完仍未找到，则输出 $False$。
 
-## 代码
+### 思路 1：代码
 
 ```python
 class Solution:
@@ -54,3 +79,8 @@ class Solution:
         return False
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$。
+- **空间复杂度**：$O(1)$。
+
diff --git a/Solutions/0845. 数组中的最长山脉.md b/Solutions/0845. 数组中的最长山脉.md
@@ -9,21 +9,50 @@
 
 ## 题目大意
 
-给定一个整数数组 `arr`。
+**描述**：给定一个整数数组 $arr$。
 
-要求：返回最长「山脉」长度。如果不含有 「山脉」 则返回 0。
+**要求**：返回最长山脉子数组的长度。如果不存在山脉子数组，返回 $0$。
 
-- 山脉：数组`arr` 中满足 `arr[i - a] < ... < arr[i - 1] < arr[i] > arr[i + 1] > ... > arr[i + b]` 的连续子数组。
+**说明**：
+
+- **山脉数组**：符合下列属性的数组 $arr$ 称为山脉数组。
+  - $arr.length \ge 3$。
+  - 存在下标 $i(0 < i < arr.length - 1)$ 满足：
+    - $arr[0] < arr[1] < … < arr[i]$
+    - $arr[i] > arr[i + 1] > … > arr[arr.length - 1]$
+
+- $1 \le arr.length \le 10^4$。
+- $0 \le arr[i] \le 10^4$。
+
+**示例**：
+
+- 示例 1：
+
+```python
+输入：arr = [2,1,4,7,3,2,5]
+输出：5
+解释：最长的山脉子数组是 [1,4,7,3,2]，长度为 5。
+```
+
+- 示例 2：
+
+```python
+输入：arr = [2,2,2]
+输出：0
+解释：不存在山脉子数组。
+```
 
 ## 解题思路
 
-- 使用变量 `ans` 保存最长山脉长度。
-- 遍历数组，假定当前节点为山峰。
-- 使用双指针 `left`、`right` 分别向左、向右查找山脉的长度。
-- 如果当前山脉的长度比最长山脉长度更长，则更新最长山脉长度。
-- 最后输出 `ans`。
+### 思路 1：快慢指针
 
-## 代码
+1. 使用变量 $ans$ 保存最长山脉长度。
+2. 遍历数组，假定当前节点为山峰。
+3. 使用双指针 $left$、$right$ 分别向左、向右查找山脉的长度。
+4. 如果当前山脉的长度比最长山脉长度更长，则更新最长山脉长度。
+5. 最后输出 $ans$。
+
+### 思路 1：代码
 
 ```python
 class Solution:
@@ -44,3 +73,8 @@ class Solution:
         return res
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $arr$ 中的元素数量。
+- **空间复杂度**：$O(1)$。
+
diff --git a/Solutions/0978. 最长湍流子数组.md b/Solutions/0978. 最长湍流子数组.md
@@ -9,26 +9,50 @@
 
 ## 题目大意
 
-给定一个数组 `arr`。当 `arr` 的子数组 `arr[i]`，`arr[i + 1]`，`...`， `arr[j]` 满足下列条件时，我们称其为湍流子数组：
+**描述**：给定一个数组 $arr$。当 $arr$ 的子数组 $arr[i]$，$arr[i + 1]$，$...$， $arr[j]$ 满足下列条件时，我们称其为湍流子数组：
 
-- 若 `i <= k < j`，当 `k` 为奇数时， `arr[k] > arr[k + 1]`，且当 `k` 为偶数时，`arr[k] < arr[k + 1]`；
-- 或若 `i <= k < j`，当 `k` 为偶数时，`arr[k] > arr[k + 1]` ，且当 `k` 为奇数时，`arr[k] < arr[k + 1]`。
+- 如果 $i \le k < j$，当 $k$ 为奇数时， $arr[k] > arr[k + 1]$，且当 $k$ 为偶数时，$arr[k] < arr[k + 1]$；
+- 或如果 $i \le k < j$，当 $k$ 为偶数时，$arr[k] > arr[k + 1]$ ，且当 $k$ 为奇数时，$arr[k] < arr[k + 1]$。
 - 也就是说，如果比较符号在子数组中的每个相邻元素对之间翻转，则该子数组是湍流子数组。
 
-要求：返回给定数组 `arr` 的最大湍流子数组的长度。
+**要求**：返回给定数组 $arr$ 的最大湍流子数组的长度。
+
+**说明**：
+
+- $1 \le arr.length \le 4 \times 10^4$。
+- $0 \le arr[i] \le 10^9$。
+
+**示例**：
+
+- 示例 1：
+
+```python
+输入：arr = [9,4,2,10,7,8,8,1,9]
+输出：5
+解释：arr[1] > arr[2] < arr[3] > arr[4] < arr[5]
+```
+
+- 示例 2：
+
+```python
+输入：arr = [4,8,12,16]
+输出：2
+```
 
 ## 解题思路
 
-湍流子数组实际上像波浪一样，比如 `arr[i - 2] > arr[i - 1] < arr[i] > arr[i + 1] < arr[i + 2]`。所以我们可以使用双指针的做法。具体做法如下：
+### 思路 1：快慢指针
 
-- 使用两个指针 `left`、`right`。`left` 指向湍流子数组的左端，`right` 指向湍流子数组的右端。
-- 如果 `arr[right - 1] == arr[right]`，则更新 `left = right`，重新开始计算最长湍流子数组大小。
-- 如果 `arr[right - 2] < arr[right - 1] < arr[right]`，此时为递增数组，则 `left` 从 `right - 1` 开始重新计算最长湍流子数组大小。
-- 如果 `arr[right - 2] > arr[right - 1] > arr[right]`，此时为递减数组，则 `left` 从 `right - 1` 开始重新计算最长湍流子数组大小。
-- 其他情况（即 `arr[right - 2] < arr[right - 1] > arr[right]` 或 `arr[right - 2] > arr[right - 1] < arr[right]`）时，不用更新 `left`值。
-- 更新最大湍流子数组的长度，并向右移动 `right`。直到 `right >= len(arr)` 时，返回答案 `ans`。
+湍流子数组实际上像波浪一样，比如 $arr[i - 2] > arr[i - 1] < arr[i] > arr[i + 1] < arr[i + 2]$。所以我们可以使用双指针的做法。具体做法如下：
 
-## 代码
+- 使用两个指针 $left$、$right$。$left$ 指向湍流子数组的左端，$right$ 指向湍流子数组的右端。
+- 如果 $arr[right - 1] == arr[right]$，则更新 `left = right`，重新开始计算最长湍流子数组大小。
+- 如果 $arr[right - 2] < arr[right - 1] < arr[right]$，此时为递增数组，则 $left$ 从 $right - 1$ 开始重新计算最长湍流子数组大小。
+- 如果 $arr[right - 2] > arr[right - 1] > arr[right]$，此时为递减数组，则 $left$ 从 $right - 1$ 开始重新计算最长湍流子数组大小。
+- 其他情况（即 $arr[right - 2] < arr[right - 1] > arr[right]$ 或 $arr[right - 2] > arr[right - 1] < arr[right]$）时，不用更新 $left$值。
+- 更新最大湍流子数组的长度，并向右移动 $right$。直到 $right \ge len(arr)$ 时，返回答案 $ans$。
+
+### 思路 1：代码
 
 ```python
 class Solution:
@@ -49,3 +73,8 @@ class Solution:
         return ans
 ```
 
+### 思路 1：复杂度分析
+
+- **时间复杂度**：$O(n)$，其中 $n$ 为数组 $arr$ 中的元素数量。
+- **空间复杂度**：$O(1)$。
+
diff --git a/Solutions/1051. 高度检查器.md b/Solutions/1051. 高度检查器.md
@@ -0,0 +1,57 @@
+# [1051. 高度检查器](https://leetcode.cn/problems/height-checker/)
+
+- 标签：数组、计数排序、排序
+- 难度：简单
+
+## 题目链接
+
+- [1051. 高度检查器 - 力扣](https://leetcode.cn/problems/height-checker/)
+
+## 题目大意
+
+**描述**：
+
+**要求**：
+
+**说明**：
+
+- 
+
+**示例**：
+
+- 示例 1：
+
+```python
+```
+
+- 示例 2：
+
+```python
+```
+
+## 解题思路
+
+### 思路 1：
+
+### 思路 1：代码
+
+```Python
+```
+
+### 思路 1：复杂度分析
+
+- **时间复杂度**：
+- **空间复杂度**：
+
+### 思路 2：
+
+### 思路 2：代码
+
+```python
+```
+
+### 思路 2：复杂度分析
+
+- **时间复杂度**：
+- **空间复杂度**：
+
