在数组中为每个元素找到下一个较小的元素

1. Overview

In this tutorial, we’ll discuss the problem of finding the next smaller element for each element in an array.

First, we’ll define the problem. Then we’ll give an example to explain it.

Finally, we’ll present two different approaches to solving this problem.

2. Defining the Problem

Suppose we have an array of length , consisting of integers, and we’re asked to find the next smaller element for each element in this array. In other words, for each index , find such index that satisfies , , and is as small as possible.

Let’s take a look at the following example:

The next smaller element for:

1. is
2. is
3.   is
4. is (there’s no next smaller)
5. is
6. is (there’s no next smaller)

3. Naive Approach

3.1. Main Idea

The main idea here is that we loop over all the elements in the given array. For each element, we’ll iterate over all the elements that come after it.

Once we find an element with a value less than the current element’s value, we’ll return it as the next smaller element for the current one. If no element has a value less than the current one, we return .

3.2. Algorithm

Let’s take a look at the implementation:

algorithm NaiveApproach(Arr):
    // INPUT
    //   Arr = an array of integers
    // OUTPUT
    //   Returns the next smaller element for each element in Arr

    next_smaller <- initialize an array of size N with -1
    for i <- 1 to N:
        for j <- i + 1 to N:
            if Arr[j] < Arr[i]:
                next_smaller[i] <- Arr[j]
                break

    return next_smaller

Firstly, we declare an array to store the next smaller element for each element.

Secondly, we loop over each element in the given array. For each of them, we then iterate over all the elements that come after it. Once we find one with a value less than the current value, we update the value for the current element to be equal to the one we found.

Finally, we break out of the loop and don’t get any smaller values than the current one.

3.3. Complexity

The complexity of this algorithm is , where is the length of the given array. This is because in the worst-case scenario, we’ll iterate over the rest of the array for each element.

4. Stack Approach

4.1. The Main Idea

The main idea in this approach is that we loop over all the elements of the given array starting from the end. We want to get the nearest element to the right that has a value smaller than its value for each of them. Furthermore, as long as we go over the elements, we keep adding them into a stack.

To get the next smaller element of the current one, we check the element located at the top of the stack. The reason is that this element is the nearest one to the current value because a stack satisfies the strategy of FIFO (First In First Out).

Then we keep popping values out of the stack, as long as it’s not empty, and the top element of the stack is larger than the current one. The moment we find an element with a smaller value, we keep it as the next smaller one. Otherwise, the stack will eventually become empty, meaning no element has a value smaller than the current one.

Note that when we pop elements out of the stack, we don’t add them back. The reason is that if we’re currently at the element, and the top of the stack contained the value since we pop the element, it means that . We already know that isn’t the next smaller value, and we can prove that it can’t be the next smaller one for any element such that .

If was larger than , then would be the next smaller value for , and we don’t need the value .

On the other hand, if was smaller than , then isn’t the next smaller element. However, we already know that is larger than . Thus, can’t be the answer to as well.

As a result, once we pop from the stack, we don’t need to add it back because it won’t be useful anymore.

4.2. Algorithm

Let’s take a look at the implementation:

algorithm StackApproach(Arr):
    // INPUT
    //   Arr = an array of integers
    // OUTPUT
    //   Returns the next smaller element for each element in Arr

    next_smaller <- initialize an array of size N with -1
    stack <- an empty stack
    for i <- N, N - 1, ..., 1:
        next_smaller[i] <- -1
        while not stack.empty() AND stack.top() >= Arr[i]:
            stack.pop()
        if not stack.empty():
            next_smaller[i] <- stack.top()
        stack.push(Arr[i])

    return next_smaller

Initially, we declare an array to store the next smaller element for each element. We also declare an empty stack to store the elements as discussed in section 4.1.

Next, we loop over all the elements from the end of to the beginning. As long as the top element in the stack has a value greater than the current one, we pop it from the stack.

After that, we check the size of the stack. If the stack isn’t empty, the top element in the stack is smaller than , and thus it’s the next smaller for the current value. Otherwise, there’s no next smaller element for the current one, so the value of would remain as .

Finally, we add the current value to the stack to use it for the next element.

4.3. Complexity

The complexity of this algorithm is , where is the length of the given array.

This is because we iterate over each element once, add it to the stack once, and also pop it from the stack at most once. Therefore, the inner loop won’t iterate more than times because, with each iteration, we pop one element from the stack.

If we don’t pop an element, then we break the loop.

5. Conclusion

In this article, we presented the problem of finding the next smaller element for each element in an array.

First, we provided an example for a better understanding of the problem. Then we explained the main ideas behind the two different approaches to solving this problem. Finally, we walked through their implementations.