Using monotonic stack to solve some questions

We can use the monotonic stack to solve some problems in O(n) efficiently. We have several such kinds of questions can be solved by using the Monotonic stack.

AcWing 830 monotonic stack

A nice explanation can be found here. The gif is pretty nice, although some part of the vis is in Chinese. Basically, that problem is trying to find the previous minimum value. If not, return -1. The vis is using the example of

Code

AcWing 3516 the maximum area in a binary matrix.

Some nice articles can be found:

https://jimmy-shen.medium.com/sliding-window-min-max-priority-queue-monotonic-queue-ec77636cdc31

Data Scientist/MLE/SWE @takemobi