Solution1 贪心 + 双指针

• 时间复杂度 O(n)

• 空间复杂度 O(1)

把 nums 分成 3 部分：ABC

设我们要找的就是 B，则 A 和 C 都是升序，且

• A 中任意元素小于 B 中最小元素

• C 中任意元素大于 B 中最大元素

寻找 B 右边界的方法：

从左往右遍历 nums，用 maxn 来记录当前（遇到 i 之前）的最大值。

• nums[i] > maxn，说明当前元素可以作为升序序列新的末尾元素。更新 maxn

• nums[i] <= maxn，说明 [0, i] 区间内的数组不满足升序条件。更新 r 到 i

即让 r 右边的 都大于 maxn

找左边界的方法正好相反，从右往左遍历。