LeetCode 题解工作台
非递减数组的最大长度
给你一个整数数组 nums 。在一次操作中，你可以选择一个子数组，并将其替换为一个等于该子数组 最大值 的单个元素。 返回经过零次或多次操作后，数组仍为 非递减 的情况下，数组 可能的最大长度 。 子数组 是数组中一个连续、 非空 的元素序列。 示例 1： 输入： nums = [4,2,5,3,5…
4
题型
5
代码语言
3
相关题
当前训练重点
中等 · 栈·状态
答案摘要
class Solution: def maximumPossibleSize(self, nums: List[int]) -> int:
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 栈·状态 题型思路
题目描述
给你一个整数数组 nums。在一次操作中，你可以选择一个子数组，并将其替换为一个等于该子数组 最大值 的单个元素。
返回经过零次或多次操作后，数组仍为 非递减 的情况下，数组 可能的最大长度。
子数组 是数组中一个连续、非空 的元素序列。
示例 1：
输入： nums = [4,2,5,3,5]
输出： 3
解释：
实现最大长度的一种方法是：
- 将子数组
nums[1..2] = [2, 5]替换为5→[4, 5, 3, 5]。 - 将子数组
nums[2..3] = [3, 5]替换为5→[4, 5, 5]。
最终数组 [4, 5, 5] 是非递减的，长度为 3。
示例 2：
输入： nums = [1,2,3]
输出： 3
解释：
无需任何操作，因为数组 [1,2,3] 已经是非递减的。
提示：
1 <= nums.length <= 2 * 1051 <= nums[i] <= 2 * 105
解题思路
方法一
class Solution:
def maximumPossibleSize(self, nums: List[int]) -> int:
ans = mx = 0
for x in nums:
if mx <= x:
ans += 1
mx = x
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) as each element is pushed and popped at most once. Space complexity is O(n) for the stack in the worst case when no merges occur. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Do you notice the decreasing sequences in nums and how to manage them?
- question_mark
Have you considered iterating backwards to simplify merge decisions with a stack?
- question_mark
Can you explain how each operation affects the final array size and order?
常见陷阱
外企场景- error
Merging forward instead of backward may require complex lookahead logic.
- error
Forgetting to update the maximum when merging subarrays can yield incorrect counts.
- error
Ignoring equal elements can reduce the array size unnecessarily.
进阶变体
外企场景- arrow_right_alt
Count minimum operations to make the array non-decreasing instead of maximum size.
- arrow_right_alt
Apply the same method to multidimensional arrays along one axis using stack-based state tracking.
- arrow_right_alt
Restrict merges to subarrays of fixed length and compute maximum non-decreasing size.