3523. Make Array Non-decreasing
Medium56.8% acceptance32,161 / 56,660 submissions
Asked by 1 company
Topics
You are given an integer array nums. In one operation, you can select a subarray and replace it with a single element equal to its maximum value.
Return the maximum possible size of the array after performing zero or more operations such that the resulting array is non-decreasing.
Example 1:
Input: nums = [4,2,5,3,5]
Output: 3
Explanation:
One way to achieve the maximum size is:
- Replace subarray
nums[1..2] = [2, 5]with5→[4, 5, 3, 5]. - Replace subarray
nums[2..3] = [3, 5]with5→[4, 5, 5].
The final array [4, 5, 5] is non-decreasing with size 3.
Example 2:
Input: nums = [1,2,3]
Output: 3
Explanation:
No operation is needed as the array [1,2,3] is already non-decreasing.
Constraints:
1 <= nums.length <= 2 * 1051 <= nums[i] <= 2 * 105
Hints
Hint 1
Iterate backwards.
Hint 2
Can you remove the largest element in the array? Is that ever helpful?