Problem

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

1
2
3
4
5
6
7

Input: nums = [4,2,5,3,5]
Output: 3
Explanation:
One way to achieve the maximum size is:
1. Replace subarray `nums[1..2] = [2, 5]` with `5` -> `[4, 5, 3, 5]`.
2. Replace subarray `nums[2..3] = [3, 5]` with `5` -> `[4, 5, 5]`.
The final array `[4, 5, 5]` is non-decreasing with size 3.

Example 2

1
2
3
4

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 * 10^5
  • 1 <= nums[i] <= 2 * 10^5

Examples

Solution

Method 1 – Monotonic Stack (Greedy)

Intuition

To maximize the size of the resulting non-decreasing array, we want to merge as few elements as possible. We can use a monotonic stack to greedily merge elements when a decrease is found, always merging the rightmost possible subarray to its maximum.

Approach

  1. Initialize an empty stack.
  2. Iterate through the array:
    • If the stack is empty or the current number is greater than or equal to the top, push it onto the stack.
    • If the current number is less than the top, pop elements from the stack until the stack is empty or the top is less than or equal to the current number, then push the maximum of the popped elements and the current number.
  3. The size of the stack at the end is the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution {
public:
    int maxArrayLength(vector<int>& nums) {
        vector<int> stk;
        for (int x : nums) {
            while (!stk.empty() && x < stk.back()) {
                x = max(x, stk.back());
                stk.pop_back();
            }
            stk.push_back(x);
        }
        return stk.size();
    }
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

func maxArrayLength(nums []int) int {
    stk := []int{}
    for _, x := range nums {
        for len(stk) > 0 && x < stk[len(stk)-1] {
            if x < stk[len(stk)-1] {
                x = max(x, stk[len(stk)-1])
            }
            stk = stk[:len(stk)-1]
        }
        stk = append(stk, x)
    }
    return len(stk)
}
func max(a, b int) int { if a > b { return a } else { return b } }
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    public int maxArrayLength(int[] nums) {
        Deque<Integer> stk = new ArrayDeque<>();
        for (int x : nums) {
            while (!stk.isEmpty() && x < stk.peekLast()) {
                x = Math.max(x, stk.pollLast());
            }
            stk.addLast(x);
        }
        return stk.size();
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

class Solution {
    fun maxArrayLength(nums: IntArray): Int {
        val stk = ArrayDeque<Int>()
        for (x0 in nums) {
            var x = x0
            while (stk.isNotEmpty() && x < stk.last()) {
                x = maxOf(x, stk.removeLast())
            }
            stk.addLast(x)
        }
        return stk.size
    }
}
1
2
3
4
5
6
7
8

class Solution:
    def maxArrayLength(self, nums: list[int]) -> int:
        stk = []
        for x in nums:
            while stk and x < stk[-1]:
                x = max(x, stk.pop())
            stk.append(x)
        return len(stk)
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

impl Solution {
    pub fn max_array_length(nums: Vec<i32>) -> i32 {
        let mut stk = Vec::new();
        for mut x in nums {
            while let Some(&top) = stk.last() {
                if x < top {
                    x = x.max(stk.pop().unwrap());
                } else {
                    break;
                }
            }
            stk.push(x);
        }
        stk.len() as i32
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

class Solution {
    maxArrayLength(nums: number[]): number {
        const stk: number[] = [];
        for (let x of nums) {
            while (stk.length && x < stk[stk.length-1]) {
                x = Math.max(x, stk.pop()!);
            }
            stk.push(x);
        }
        return stk.length;
    }
}

Complexity

  • ⏰ Time complexity: O(n), as each element is pushed and popped at most once.
  • 🧺 Space complexity: O(n), for the stack.