Monotonic Stack: Steps to Make Array Non-decreasing
Problem
Given an integer array A, in one step, remove all elements A[i] where A[i-1] > A[i].
Return the number of steps performed until A becomes a non-decreasing array.
See examples at LeetCode 2289.
Solution
The naive approach executes steps one by one. Store integers in a Linked List. At each step, find all integers that are smaller than its left neighbor and remove them. However, the time complexity is O(n^2) because each step may remove just one integer. For example, [1000, 1, 2, 3, ...., 999].
We need to look for key observations. First, it is easy to know which integers needs to be removed. All integers that is not in the final non-decreasing array needs to go. Moreover, the remaining integers separate the original array into subarrays and each each subarray can go through the removal steps independently. For example, [5, 4, 3, 2, 11, 10, 8, 9 11] has two subarrays to remove, [4, 3, 2] and [10, 8, 9]. This observation means that we can start refresh whenever we see an integer than cannot be removed.
Let f[i] be the order of step when A[i] is removed. If there is a longest decreasing subarray ends at A[j], say, A[i] > A[i+1] > A[i+2] > ... > A[j] and A[i] <= A[j+1], then f[i+1]=f[i+2]=...=f[j] and f[j+1]=f[i+1]+1. This observation of longest deceasing subarray can be applied recursively, after removal of A[i+1:j]. In order to handle the "removal" recursively, we use a stack. In order to calculate f[i], we store the index of the array in the stack.
1func totalSteps(a []int) int {
2 n := len(a)
3 f := make([]int, n)
4 stack := []int{}
5 maxStep := 0
6 for i, v := range a {
7 step := 0
8 // pop from stack if needed, to make sure a[i] can be appended to the decreasing stack.
9 for {
10 m := len(stack)
11 if m == 0 || v < a[stack[m-1]] {
12 break
13 }
14 step = max(step, f[stack[m-1]]+1)
15 stack = stack[:m-1]
16 }
17
18 if len(stack) > 0 {
19 f[i] = max(1, step) // a[i] needs to be removed, so f[i] is at least 1.
20 maxStep = max(maxStep, f[i])
21 } else {
22 f[i] = 0 // a[i] does not need to be removed because there is no larger integer on its left side.
23 }
24
25 // push to stack
26 stack = append(stack, i)
27 }
28 return maxStep
29}