单调栈、单调队列


前言

本文介绍单调栈和单调队列的使用,并且提供模板。

一、单调栈?

栈地到栈顶是单调增加或者单调减少的。

1.代码模板:

//常见模型:找出每个数左边离它最近的比它大/小的数
//stk[0]是不存放元素的,stk[tt]存放栈顶元素
int tt = 0;
for (int i = 1; i <= n; i ++ )
{
    while (tt && check(stk[tt], i)) tt -- ;	//根据栈的后进先出特点,弹出的栈顶元素一定是离i最近且比他小/大的元素
    stk[ ++ tt] = i;
}

2.例题LeetCode316

316. 去除重复字母 给你一个字符串 s ,请你去除字符串中重复的字母,使得每个字母只出现一次。需保证 返回结果的字典序最小(要求不能打乱其他字符的相对位置)。

示例 1:

输入:s = "bcabc"
输出:"abc"
示例 2:

输入:s = "cbacdcbc"
输出:"acdb"

[分析]
若输入为bcacc

  1. b 入栈
  2. c 入栈时因为字典序靠后,且栈中没出现过c,直接压栈
  3. a 入栈,因为 a 的字典序列靠前且栈中a没有出现过,此时要考虑弹出栈顶元素.
    元素 c 因为在之后还有 至少一次 出现次数,所以这里可以弹出.
    元素 b 之后不再出现,为了保证至少出现一次这里不能再舍弃了.
  4. c 入栈时依然因为字典序靠后且栈中没出现过直接压栈
  5. c 入栈时栈中已经出现过c,跳过该元素
    输出结果为 bac

    [解答]
    public String removeDuplicateLetters(String s) {
        char[] chars = s.toCharArray();
        int[] count = new int[26];
        for (int i = 0; i < chars.length; i++) {
            count[chars[i] - ‘a‘]++;
        }
        boolean[]exists = new boolean[26];
        //模板
        int tt = 0;
        int[] stk = new int[s.length() + 1];
        for (int i = 0; i < chars.length; i++) {
            if(!exists[chars[i] - ‘a‘]) {
                while (tt != 0 && (stk[tt] > chars[i] && count[stk[tt] - ‘a‘] > 0)) { //根据栈的后进先出特点,弹出的栈顶元素一定是比入栈元素大,且后续还有该元素
                    exists[stk[tt] - ‘a‘] = false;
                    tt--;
                }
                //入栈
                stk[++tt] = chars[i];
                exists[chars[i] - ‘a‘] = true;
            }
            count[chars[i] - ‘a‘]--;
        }
        StringBuilder sb=new StringBuilder();
        for (int i = 1; i <= tt; i++) { //stk[0]是不存放元素的,stk[tt]存放栈顶元素
            sb.append((char) stk[i]);
        }
        return sb.toString();
    }

3.单调栈经典题目

给定一个长度为N的整数数列,输出每个数左边第一个比它小的数,如果不存在则输出-1。
输入格式
第一行包含整数N,表示数列长度。
第二行包含N个整数,表示整数数列。
输出格式
共一行,包含N个整数,其中第i个数表示第i个数的左边第一个比它小的数,如果不存在则输出-1。
数据范围
1≤N≤105
1≤数列中元素≤109
输入样例:
5
3 4 2 7 5
输出样例:
-1 3 -1 2 2

    public void findMin(int[] arr,int n){
        int[] stk=new int[n+1];
        int tt = 0;
        for(int i = 0; i<n; i++)
        {
            int x=arr[i];
            while (tt!=0 && stk[tt] >= x) tt--;	//把栈中大于等于x的数剔除,此时栈中只有小于x的数
            if(tt!=0) System.out.printf("%d ", stk[tt]);	//如果栈不为空,输出栈顶元素,即离x最近且小于x的值
            else System.out.printf("-1 ");	//如果栈为空,输出-1
            stk[++tt] = x;		//把x插入栈中
        }
    }

二、单调队列

1.模板

代码如下(示例):

常见模型:找出滑动窗口中的最大值/最小值
int hh = 0, tt = -1;
for (int i = 0; i < n; i ++ )
{
    while (hh <= tt && check_out(q[hh])) hh ++ ;  // 判断队头是否滑出窗口
    while (hh <= tt && check(q[tt], i)) tt -- ;		//判断队尾是否满足要求
    q[ ++ tt] = i;
}
原理:利用一个循环控制队头,利用一个循环控制队尾,队头决定队的长度,队尾控制队列中的序列单调

2.滑动窗口求值

给定一个大小为n≤10^6的数组。 有一个大小为k的滑动窗口,它从数组的最左边移动到最右边。 您只能在窗口中看到k个数字。 每次滑动窗口向右移动一个位置。 以下是一个例子: 该数组为[1 3 -1 -3 5 3 6 7],k为3。

您的任务是确定滑动窗口位于每个位置时,窗口中的最大值和最小值。
输入格式
输入包含两行。
第一行包含两个整数n和k,分别代表数组长度和滑动窗口的长度。
第二行有n个整数,代表数组的具体数值。
同行数据之间用空格隔开。
输出格式
输出包含两个。
第一行输出,从左至右,每个位置滑动窗口中的最小值。
第二行输出,从左至右,每个位置滑动窗口中的最大值。
输入样例:
8 3
1 3 -1 -3 5 3 6 7
输出样例:
-1 -3 -3 -3 3 3
3 3 5 5 6 7
单调栈、单调队列
[解答:]

    public void minWindows(int arr[],int k){
        // 队列里面存的是下标
        int n=arr.length;
        int[] q=new int[n+1];
        //模板
        int hh = 0, tt = -1;
        for (int i = 0; i < n; i ++ )
        {
            while (hh <= tt && i - k + 1 > q[hh]) hh ++ ;  // 判断队头是否滑出窗口
            while (hh <= tt && arr[q[tt]] >= arr[i]) tt -- ;		//判断队尾是否满足要求
            q[ ++ tt] = i;
            if(i >= k - 1) System.out.printf("%d ", arr[q[hh]]);		//当窗口中有k个数时从队头开始输出
        }
    }

    public void maxWindows(int arr[],int k){
        // 队列里面存的是下标
        int n=arr.length;
        int[] q=new int[n+1];
        //模板
        int hh = 0, tt = -1;
        for (int i = 0; i < n; i ++ )
        {
            while (hh <= tt && i - k + 1 > q[hh]) hh ++ ;  // 判断队头是否滑出窗口
            while (hh <= tt && arr[q[tt]] <= arr[i]) tt -- ;		//判断队尾是否满足要求
            q[ ++ tt] = i;
            if(i >= k - 1) System.out.printf("%d ", arr[q[hh]]);		//当窗口中有k个数时从队头开始输出
        }
    }


总结

灵活使用模板注意:该模板是由c++ 改动来的,所以创建队列大小时,记得确定数组的大小。

单调栈、单调队列

上一篇:LeetCode-155-最小栈


下一篇:ClickHouse集群搭建和使用