Medium

题目描述

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

提示：

  • 从后向前遍历。
  • 你能移除数组中的最大元素吗？这是否有帮助？

解题思路

这是一个贪心算法问题，需要从右向左遍历数组来构建最优解。

核心思路：

我们从右向左遍历数组，维护一个单调递增的栈。当遇到一个元素时，我们需要决定是否将其与右边的某些元素合并。

算法步骤：

  1. 从右向左遍历数组，使用栈来维护当前的非递减序列
  2. 对于每个元素 nums[i]，我们需要检查它是否能够直接加入栈中
  3. 如果 nums[i] 大于栈顶元素，说明违反了非递减性质，我们需要将栈中所有小于 nums[i] 的元素弹出
  4. 被弹出的元素实际上被"合并"到了当前元素中，因为我们可以选择一个包含这些元素的子数组，将其替换为最大值

关键观察：

  • 当我们从右向左处理时，如果当前元素比右边已确定的元素大，那么我们可以选择将它们合并
  • 合并操作总是选择子数组的最大值，这样可以最大化保留元素的数量
  • 使用栈可以高效地维护当前的非递减序列

这个贪心策略是最优的，因为我们总是尽可能保留更多的元素，只有在必要时才进行合并。

代码实现

class Solution {
public:
    int maximumPossibleSize(vector<int>& nums) {
        vector<int> stack;
        
        for (int i = nums.size() - 1; i >= 0; i--) {
            while (!stack.empty() && stack.back() < nums[i]) {
                stack.pop_back();
            }
            stack.push_back(nums[i]);
        }
        
        return stack.size();
    }
};

class Solution:
    def maximumPossibleSize(self, nums: List[int]) -> int:
        stack = []
        
        for i in range(len(nums) - 1, -1, -1):
            while stack and stack[-1] < nums[i]:
                stack.pop()
            stack.append(nums[i])
        
        return len(stack)

public class Solution {
    public int MaximumPossibleSize(int[] nums) {
        List<int> stack = new List<int>();
        
        for (int i = nums.Length - 1; i >= 0; i--) {
            while (stack.Count > 0 && stack[stack.Count - 1] < nums[i]) {
                stack.RemoveAt(stack.Count - 1);
            }
            stack.Add(nums[i]);
        }
        
        return stack.Count;
    }
}

var maximumPossibleSize = function(nums) {
    const stack = [];
    
    for (let i = nums.length - 1; i >= 0; i--) {
        while (stack.length > 0 && stack[stack.length - 1] < nums[i]) {
            stack.pop();
        }
        stack.push(nums[i]);
    }
    
    return stack.length;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)每个元素最多被压入和弹出栈一次
空间复杂度O(n)栈的最大大小为n