Skip to content

2289. Steps to Make Array Non-decreasing 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution {
 public:
  int totalSteps(vector<int>& nums) {
    // dp[i] := the number of steps to remove nums[i]
    vector<int> dp(nums.size());
    stack<int> stack;

    for (int i = 0; i < nums.size(); ++i) {
      int step = 1;
      while (!stack.empty() && nums[stack.top()] <= nums[i])
        step = max(step, dp[stack.top()] + 1), stack.pop();
      if (!stack.empty())
        dp[i] = step;
      stack.push(i);
    }

    return ranges::max(dp);
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
  public int totalSteps(int[] nums) {
    // dp[i] := the number of steps to remove nums[i]
    int[] dp = new int[nums.length];
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < nums.length; ++i) {
      int step = 1;
      while (!stack.isEmpty() && nums[stack.peek()] <= nums[i])
        step = Math.max(step, dp[stack.pop()] + 1);
      if (!stack.isEmpty())
        dp[i] = step;
      stack.push(i);
    }

    return Arrays.stream(dp).max().getAsInt();
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
class Solution:
  def totalSteps(self, nums: list[int]) -> int:
    # dp[i] := the number of steps to remove nums[i]
    dp = [0] * len(nums)
    stack = []

    for i, num in enumerate(nums):
      step = 1
      while stack and nums[stack[-1]] <= num:
        step = max(step, dp[stack.pop()] + 1)
      if stack:
        dp[i] = step
      stack.append(i)

    return max(dp)