Solutions CS101

Appearance

M3523.非递减数组的最大长度 ​

greedy, monotonic stack, https://leetcode.cn/problems/make-array-non-decreasing/

给你一个整数数组 nums。在一次操作中，你可以选择一个子数组，并将其替换为一个等于该子数组 最大值 的单个元素。

返回经过零次或多次操作后，数组仍为 非递减 的情况下，数组 可能的最大长度。

子数组 是数组中一个连续、非空 的元素序列。

示例 1：

输入： nums = [4,2,5,3,5]

输出： 3

解释：

实现最大长度的一种方法是：

  1. 将子数组 nums[1..2] = [2, 5] 替换为 5 → [4, 5, 3, 5]。
  2. 将子数组 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 * 10^5
  • 1 <= nums[i] <= 2 * 10^5
python
from typing import List

class Solution:
    def maximumPossibleSize(self, nums: List[int]) -> int:
        if not nums:
            return 0

        current_max = nums[0]
        count = 1

        for num in nums[1:]:
            if num >= current_max:
                count += 1
                current_max = num
            else:
                current_max = max(current_max, num)

        return count

if __name__ == "__main__":
    sol = Solution()
    print(sol.maximumPossibleSize([4,2,5,3,5]))
    print(sol.maximumPossibleSize([1,2,3]))