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

Initialize an empty stack.
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.
The size of the stack at the end is the answer.

Code

[{"language":"C++","code":"class Solution {\npublic:\n    int maxArrayLength(vector<int>& nums) {\n        vector<int> stk;\n        for (int x : nums) {\n            while (!stk.empty() && x < stk.back()) {\n                x = max(x, stk.back());\n                stk.pop_back();\n            }\n            stk.push_back(x);\n        }\n        return stk.size();\n    }\n};","lang":"cpp","html":"<pre class=\"shiki shiki-themes github-light github-dark\" style=\"background-color:#fff;--shiki-dark-bg:#24292e;color:#24292e;--shiki-dark:#e1e4e8\" tabindex=\"0\"><code><span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">class</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> Solution</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">public:</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">    int</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\"> maxArrayLength</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">(</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">vector</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">&#x3C;</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">></span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x26;</span><span style=\"color:#E36209;--shiki-dark:#FFAB70\"> nums</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">) {</span></span>\n<span class=\"line\"><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">        vector</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">&#x3C;int></span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> stk;</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">        for</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">int</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> x : nums) {</span></span>\n<span class=\"line\"><span style=\"color:#D73A49;--shiki-dark:#F97583\">            while</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\"> (</span><span style=\"color:#D73A49;--shiki-dark:#F97583\">!</span><span style=\"color:#24292E;--shiki-dark:#E1E4E8\">stk.</span><span style=\"color:#6F42C1;--shiki-dark:#B392F0\">empty</span>&#x

Related Tags