2289. Steps to Make Array Non-decreasing
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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public:
int totalSteps(vector<int>& nums) {
int res = 0, n = nums.size();
vector<pair<int, int>> st;
for(int i = n - 1; i >= 0; i--) {
int count = 0;
while(!st.empty() and st.back().first < nums[i]) {
count = max(count + 1, st.back().second);
st.pop_back();
}
res = max(res, count);
st.push_back({nums[i], count});
}
return res;
}
};
|
