单调栈 (Monotone Priority Stack)

单调栈

单调栈如其名，在栈中的元素都按递增或者递减的顺序进行排序，而在解题过程中使用单调栈的好处就是因为单调栈的时间复杂度是线性的，每个元素就只会遍历一遍。

模板：

常见模型：找出每个数左边离它最近的比它大/小的数
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;
    stk[ ++ tt] = i;
}

如: acwing 830. 单调栈

给定一个长度为 N 的整数数列，输出每个数左边第一个比它小的数，如果不存在则输出 −1。

输入格式

第一行包含整数 N，表示数列长度。

第二行包含 N 个整数，表示整数数列。

输出格式

共一行，包含 N 个整数，其中第 i 个数表示第 i 个数的左边第一个比它小的数，如果不存在则输出 −1。

数据范围

1≤N≤1051≤N≤105
1≤数列中元素≤1091≤数列中元素≤109

输入样例：

5
3 4 2 7 5

输出样例：

-1 3 -1 2 2

用普通做法是这样的：

用一个指针i指向当前需要处理的元素，指针j将前对前面的元素进行遍历，最终找出答案。

但是每次用j遍历前面的元素都会使得重复的遍历了相同的元素，导致时间复杂度飙升。

所以需要利用单调栈进行解题。

思路：

单调栈中的元素是我们遍历数列时放入并且按单调递增的顺序排好序的，所以每次进行判断的时候只需要取出栈顶元素即可，栈顶元素就是第一个小于当前遍历元素的数。

接下来就难在如何使得栈内元素单调。

我们需要在每个元素进栈之前进行判断，如果栈不为空，并且栈顶元素比待处理的元素大的话就需要进行出栈操作，知道栈为空或者出现比当前待处理的元素小的元素，就终止循环，将该元素放到栈中。

题解：

import java.util.Scanner;
public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] stk = new int[n];
        int tt= 0;
        for (int i = 0; i < n; i ++) {
            int x = sc.nextInt();
            while (tt != 0 && stk[tt] >= x) tt--;
            if (tt != 0) {
                System.out.print(stk[tt] + " ");
            } else {
                System.out.print(-1 + " ");
            }
            stk[++tt] = x;
        }
    }
}

栈内的元素种类可以根据题目灵活设置，只要满足单调性即可。比如下面这道题，栈内元素时数组的下标值。

leetcode 1475. 商品折扣后的最终价格

题目的意思就是给我们一个数组，找出数组中的每个数后面第一个小于它的数，并作差，如果没有，就是该数本身。

还是先创建一个栈，也可以使用jdk中的Stack类进行辅助。

然后开始依次遍历数组中的元素，在将数组中的元素进行遍历之前需要先进行判断，也就是当栈不为空的时候，并且当前遍历的元素小于或者等于栈顶元素时(此时栈内元素是单调递增的)，我们需要进行更新操作和出栈操作。

题解：

class Solution {
    public int[] finalPrices(int[] prices) {
        int n = prices.length;
        int[] stk = new int[n];
        int t = -1;
        for (int i = 0; i < n; i++) {
            while (t != -1 && prices[i] <= prices[stk[t]]) {
                prices[stk[t]] = prices[stk[t]] - prices[i];
                t--;
            }
            stk[++t] = i;
        }
        return prices; 
    }
}