2289. Steps to Make Array Non-decreasing | LeetCode Solution
You are given a 0-indexed integer array nums
. In one step, remove all elements nums[i]
where nums[i - 1] > nums[i]
for all 0 < i < nums.length
.
Return the number of steps performed until nums
becomes a non-decreasing array.
Example 1:
Input: nums = [5,3,4,4,7,3,6,11,8,5,11] Output: 3 Explanation: The following are the steps performed: - Step 1: [5,3,4,4,7,3,6,11,8,5,11] becomes [5,4,4,7,6,11,11] - Step 2: [5,4,4,7,6,11,11] becomes [5,4,7,11,11] - Step 3: [5,4,7,11,11] becomes [5,7,11,11] [5,7,11,11] is a non-decreasing array. Therefore, we return 3.
Example 2:
Input: nums = [4,5,7,7,13] Output: 0 Explanation: nums is already a non-decreasing array. Therefore, we return 0.
Constraints:
1 <= nums.length <= 105
1 <= nums[i] <= 109
class Solution {
public:
int totalSteps(vector<int>& nums) {
int ans=0;
stack<int>st;
vector<int>dp(nums.size(),0);
vector<int>v(nums.size(),-1);
for(int i=nums.size()-1; i>=0; i--){
while(!st.empty() && nums[st.top()]<nums[i]){
dp[i]=max(dp[i]+1,dp[st.top()]);
st.pop();
}
st.push(i);
ans=max(ans,dp[i]);
}
return ans;
}
};
0 Comments
If you have any doubts/suggestion/any query or want to improve this article, you can comment down below and let me know. Will reply to you soon.