Minmum Steps to Make Array Non Decreasing

• Minmum Steps to Make Array Non Decreasing
  • Description
  • Intuition
  • Solution
  • Reference

Description

Here

Intuition

If we have already make [0, i - 1] using the min steps, what should we do with the nums[i]?

1. If nums[i] >= maxInTheResultArray
   1. 这个可以坐下，是正常操作，直接append到现在的array
2. If nums[i] < maxInTheResultArray
   1. 这个时候我们有两种选择，
      1. 将nums[i] increase到 maxInTheResultArray, so steps = maxInTheResultArray - nums[i] and we will append an maxInTheResultArray
      2. 将所有的大于nums[i] decrease到nums[i]，但是此种方法，steps至少是maxInTheResultArray - nums[i]
   2. 无论那种情况，steps都相同

Solution

Here

Reference

geeks for geeks