CODEWITHSUNDEEP
c++algorithmstack
J. Doe
J. Doe

Reputation: 857

How do I solve it with a monotonic stack?

I am solving a question "Steps to Make Array Non-decreasing" on LeetCode here. Question is:

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.
Input: nums = [5,3,4,4,7,3,6,11,8,5,11]
Output: 3

During the contest I got the intuition to solve it using a monotonic stack. I tried to solve it by keeping track of the next greater element (nge) and previous greater element (pge) for each element as below:

class Solution {
public:
    int totalSteps(vector<int>& nums) {
        int n=nums.size();
        vector<int> nge(n), pge(n);
        stack<int> stk, stk2;
        
        for(int i=n-1; i>=0; i--) {
            while(stk.size() && nums[stk.top()]<nums[i]) stk.pop();
            nge[i]=stk.size() ? stk.top() : n;
            stk.push(i);
        }

        int res=0;
        for(int i=0; i<nums.size(); i++) {
            res=max(res, nge[i]-i-1);
        }
        
        for(int i=0; i<n; i++) {
            while(stk2.size() && nums[stk2.top()]<nums[i]) stk2.pop();
            pge[i]=stk2.size() ? stk2.top() : -1;
            stk2.push(i);
        }

        int ans=0;
        for(int i=0; i<nums.size(); i++) {
            ans=max(ans, i-pge[i]);
        }

        return min(res,ans);
    }
};

However it continues to yield wrong answers. Any tips on how I could solve it?

Thanks!

Upvotes: 2

Views: 581

Answers (1)

sigma
sigma

Reputation: 2953

I would go for a simpler algorithm like the one suggested by John Bayko. But, to make it fun, when thinking about algorithms I usually try to find the most appropriate standard library tools to compose them. So, here's how I might start with a short function to find the next iterator in nums to copy from, given a "current" iterator:

#include <algorithm>
#include <functional>
#include <ranges>

int totalSteps(std::vector<int>& nums) {
    namespace rng = std::ranges;

    auto nextOne = [&nums](auto current) {
        return rng::adjacent_find(current, nums.end(), rng::greater{});
    };

    // ...
}

Is this suggestive enough?

Upvotes: 0

Related Questions