This is the 10th day of my participation in the August More Text Challenge

Preface

Following the previous article about using arrays to simulate stacks and queues, today we’ll talk about monotonous stacks.

A monotone stack is one in which the elements are monotone. As we all know, if a binary equation of one degree has monotonicity, the graph shows an increasing or decreasing line, and the stack can also have increasing or decreasing monotonicity.

Properties of monotone stack:

  1. Inserting an element removes the monotonic element at the top of the stack, if there are more than one.
  2. Using monotone stack to insert elements one by one, you can find the first smaller (larger) element that the element traverses to the left.
  3. Usually used to find the largest (smallest) element of the nearest element.

Simulation

Let’s simulate a monotonically increasing stack directly: an array [4,9,5,7,12] is pushed from left to right, keeping the stack monotonically increasing:

  1. When I get to 4, the stack is empty, so I’m going to push it4 。
  2. If you go to 9, 9 is bigger than 4, 9 is the new element at the top of the stack, and the element in the stack is4, 9 。
  3. So we go to 5, 5 is less than 9, 9 goes off the stack, 5 is more than 4, 5 goes on the stack, and then the element in the stack is4, 5 。
  4. We go to 7,7 is bigger than 5, and we push it, and the top element of the stack is4，5，7 。
  5. We go to 12,12 is bigger than 7, we push it, and the top element of the stack is4，5，7，12 。

We can use this process to write pseudo code:

 for(traversing the array) {// A monotonic stack does not have the same element, greater than or equal to the stack must be removed
     whileThe top element of the stack is greater than or equal to the current element to be inserted. } into the stack; }// Write this way to save the stack empty process
Copy the code

Problem

Consider this problem: Given a series of integers of length N, print the first number to the left of each number less than it, or −1 if none exists.

Input: The first line contains the integer N, which represents the length of the sequence. The second row contains N integers, representing the integer sequence.

Output: A line containing N integers, where the i-th number is the first number to the left of the i-th number less than it. If it does not exist, the output is −1.

// Input example 5 3 4 2 7 5 // Output example -1 3-1 2 2Copy the code

Solution

Analysis: find the first smaller number on the left, it is a monotonically increasing stack! When an element can be pushed onto the stack, the top element is the first smaller element on the left:

// Created by hrh on 2021/8/27
#include <bits/stdc++.h>
using namespace std;

const int N = 1e5+10;		// Data range requirements, i.e. 100010
int stk[N], tt, n, x;		// Use array to simulate stack, tt is the top pointer of stack

int main(a) {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> x;
        while(tt && stk[tt] >= x) tt--;		/ / out of the stack
        
        if (tt) cout << stk[tt] << ' ';		// The stack is not empty output the top element of the stack
        else cout << - 1 << ' ';			// If the stack is empty, there is no smaller element on the left
        
        stk[++tt] = x;				/ / into the stack}}// If you don't understand, you can look at the pseudo-code
// C/C++ if(tt), tt>0 is true
Copy the code

Conclusion

The code idea comes from AcWing, and after reading it, you should have a general understanding of what monotone stack is and how it is used.

LeetCode (leetcode-cn.com)

If you still have no idea, you can follow me. I will update the detailed solution of several problems in these two days.

All see here, a thumbs up bai 😆

Have any question can comment message ~ can pay attention to each other exchange

More interesting articles: Mancuoj’s homepage – Articles – Nuggets (juejin. Cn)