3523. 非递减数组的最大长度

English Version

题目描述

给你一个整数数组 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 * 105
• 1 <= nums[i] <= 2 * 105

解法

方法一

Python3

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

Java

class Solution {
    public int maximumPossibleSize(int[] nums) {
        int ans = 0, mx = 0;
        for (int x : nums) {
            if (mx <= x) {
                ++ans;
                mx = x;
            }
        }
        return ans;
    }
}

C++

class Solution {
public:
    int maximumPossibleSize(vector<int>& nums) {
        int ans = 0, mx = 0;
        for (int x : nums) {
            if (mx <= x) {
                ++ans;
                mx = x;
            }
        }
        return ans;
    }
};

Go

func maximumPossibleSize(nums []int) int {
	ans, mx := 0, 0
	for _, x := range nums {
		if mx <= x {
			ans++
			mx = x
		}
	}
	return ans
}

TypeScript

function maximumPossibleSize(nums: number[]): number {
    let [ans, mx] = [0, 0];
    for (const x of nums) {
        if (mx <= x) {
            ++ans;
            mx = x;
        }
    }
    return ans;
}