#Coding-Tools View

单调栈

What is monotonous increase stack?

Roughly speaking, the elements in the an monotonous increase stack keeps an increasing order.

The typical paradigm for monotonous increase stack:

for(int i = 0; i < A.size(); i++)
{
  while(!in_stk.empty() && in_stk.top() > A[i]) // 如果栈非空且栈顶元素大于当前元素A[i]
  {
    in_stk.pop();
  }
  in_stk.push(A[i]);
}

What can monotonous increase stack do?

(1) find the previous less element (PLE) of each element in a vector with O(n) time:

What is the previous less element of an element?

For example:
[3, 7, 8, 4]
The previous less element of 7 is 3.
The previous less element of 8 is 7.
The previous less element of 4 is 3.
There is no previous less element for 3.

C++ code (by slitghly modifying the paradigm):

Instead of directly pushing the element itself, here for simplicity, we push the index.
We do some record when the index is pushed into the stack.

   // previous_less[i] = j means A[j] is the previous less element of A[i].
  // previous_less[i] = -1 means there is no previous less element of A[i].
 vector<int> previous_less(A.size(), -1);
 for(int i = 0; i < A.size(); i++)
 {
       while(!in_stk.empty() && A[in_stk.top()] > A[i])
       {
           in_stk.pop();
       }
 
       previous_less[i] = in_stk.empty()? -1: in_stk.top();
       in_stk.push(i);
}

(2) find the next less element (NLE) of each element in a vector with O(n) time:

What is the next less element of an element ?

For example:
[3, 7, 8, 4]
The next less element of 8 is 4.
The next less element of 7 is 4.
There is no next less element for 3 and 4.

C++ code (by slighly modifying the paradigm):

We do some record when the index is poped out from the stack.

// next_less[i] = j means A[j] is the next less element of A[i].
// next_less[i] = -1 means there is no next less element of A[i].
vector<int> previous_less(A.size(), -1);
for(int i = 0; i < A.size(); i++)
{
    while(!in_stk.empty() && A[in_stk.top()] > A[i])
    {
        auto x = in_stk.top(); 
        in_stk.pop();
        next_less[x] = i;
    }
    in_stk.push(i);
}