Leetcode 2289. Steps to Make Array Non-decreasing

[Woodyiiiiiii]

这道题我的想法是，一个数组中维护多个stack，最后合并，但这样写出来肯定不对，所以该用数组dp来存储，dp[i]表示能i位置能吞并的最大值。

其次，关键是iterate reversely。

然后维护一个单调栈。

class Solution {
    public int totalSteps(int[] nums) {
        int n = nums.length, ans = 0;
        int[] dp = new int[n];
        LinkedList<Integer> stack = new LinkedList<>();
        for (int i = n - 1; i >= 0; --i) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                dp[i] = Math.max(++dp[i], dp[stack.pop()]);
                ans = Math.max(ans, dp[i]);
            }
            stack.push(i);
        }
        return ans;
    }
}

---

• 2289. Steps to Make Array Non-decreasing