首页 > 「面向 offer 学算法」笔面试大杀器 -- 单调栈
头像
泼墨一纸江南
编辑于 2020-09-10 15:26
+ 关注

「面向 offer 学算法」笔面试大杀器 -- 单调栈

目录

  1. 前言
  2. 单调栈
  3. 初入茅庐
  4. 小试牛刀
  5. 打怪升级
  6. 出师试炼

前言

(原文的初入茅庐段落有错误,现已修正,向各位读者说声抱歉。)

单调栈是一种比较简单的数据结构。虽然简单,但在某些题目中能发挥很好的作用。

最近很多大厂的笔试、面试中都出现了单调栈的题目,而还有不少小伙伴连单调栈是什么都不了解,因此老汪专门写了这篇文章,希望对你们有所帮助。

老规矩,先上一道题给大家看看单调栈能解决什么样的问题,这题是 2020 年猿辅导(K12 教育的独角兽,研发岗白菜价 40W 起步,不加班高福利,想要内推的可以私信老汪)的一道面试题。

给定一个二叉搜索树,并给出他的前序序列,要求输出中序序列,时间复杂度O(n),并给出证明。

单调栈

  • 是什么:单调栈是一种具有单调性的栈,任何时刻从栈顶到栈底的元素都是单调增/减的。
  • 干什么:
    • 单调栈可以找到从左/右遍历第一个比它大/小的元素的位置。
    • 单调栈也可以将某个元素左/右边所有比它小/大的元素按升/降序输出。
  • 怎么做:使用栈结构,在入栈的时候保持 id 和 val 的单调性即可。

翻译成大白话,凡是遇到题目中直接或间接要求查找某个元素左/右边第一个大于/小于它的元素,或者要求将某个元素左/右边所有小/大于它的元素按升/降序输出,就可以使用单调栈来解决。

具体怎么做你可能还有些迷糊,下面我们直接通过做题来加深对单调栈的理解。十分钟包教包会,当天就可以和面试官对线。

初入茅庐

给定数组 a,要求输出这样的数组 b,b[i] 是 a[i] 左边第一个比 a[i] 大的元素,若不存在则 b[i] = a[i]。

最暴力的解法,就是对每一个 a[i],遍历其左边的所有元素,这样所需的时间复杂度是 O(n^2)。如果使用单调栈,时间复杂度可以优化到 O(n)。

这是最基本、最直白的单调栈问题,所有单调栈问题都是在该问题上进行延伸、变种得来的,掌握了这个问题的解决方法,所有单调栈的问题都能迎刃而解

由于本问题过于简单、直白,就不多做讲解,直接上代码:

public int[] solve(int[] a){
  if(a == null) return null; //容错处理,越是简单的题越要注意细节
  int n = a.length;
  int[] b = new int[n];
  Stack<Integer> stack = new Stack(); //单调栈当然要用栈结构啦
  for(int i = 0; i < n; i++){
    while(!stack.isEmpty() && stack.peek() < a[i]) stack.pop(); //所有比 a[i] 小的元素都出栈,保证了从栈顶到栈底元素是单调增的,并且栈顶的元素是 a[i] 左边第一个比 a[i] 大的元素
    b[i] = stack.isEmpty() ? a[i] : stack.peek();
    stack.push(a[i]);
  }
  return b;
}

这代码也是单调栈问题的基本结构,所有单调栈问题的代码都基于此进行变种、扩展。小伙伴们可以多花两分钟好好消化上面的代码。

考虑到有些小伙伴不用 Java,老汪把上述代码抽象成伪代码,这也是单调栈的基本结构

背诵 + 套用,即可解决所有单调栈问题。

函数 solve (数组 a):
    新建数组 b;
    新建栈 stack;
    For i From 0 To n - 1:
        While 栈非空 且 栈顶元素 < a[i]:
            出栈;
        End While
        b[i] = 栈顶元素 IF 栈非空 ELSE 默认值;
        a[i] 入栈;
    End For
    return b;

小试牛刀

单调栈的最基本使用方式我们已经了解了,下面一起来解决文章开头提到的面试题。

给定一个二叉搜索树,并给出他的前序序列,要求输出中序序列,时间复杂度O(n),并给出证明。

最暴力的方法就是对前序序列进行排序,时间复杂度为 O(nlogn),使用单调栈可以优化到 O(n)。

思路分析:

对于二叉搜索树而言,给定其根节点 a[i],左子树里所有元素都比 a[i] 小,右子树里所有元素都比 a[i] 大。

回顾一下遍历顺序:

前序序列,先遍历根节点,再遍历左子树,最后遍历右子树;

中序序列,先遍历左子树,再遍历根节点,最后遍历右子树。

即,对于元素 a[i],以它为根节点的子树,

前序序列为,a[i], a[i] 的左子树序列, a[i] 的右子树序列

后序序列为,a[i] 的左子树序列, a[i]a[i] 的右子树序列

因此,当我们遍历前序序列,遇到右子树的第一个元素 a[j] 时,其左边所有元素都小于 a[j], 将其左边所有元素按升序输出,即可得到 a[i]a[i] 的左子树 的后序序列。

对于右子树再以上述步骤迭代,即可得到完整的后序序列。

显然,这是单调栈的第二种用法:单调栈可以将某个元素左边所有比它小的元素按升序输出。

下面直接上代码:

public int[] solve(int[] pre){
  if(pre == null) return null; //注意容错细节
  int n = pre.length;
  int[] infix = new int[n]; //中序序列
  Stack<Integer> stack = new Stack();
  int index = 0; // 指示中序序列的当前下标
  for(int i = 0; i < n; i++){
    while(!stack.isEmpty() && stack.peek() < pre[i]) infix[index++] = stack.pop(); //由于栈中元素是从栈顶到栈底单调增的,所以可以保证输出序列是单调增的
    stack.push(pre[i]);
  }
  while(!stack.isEmpty()) infix[index++] = stack.pop();
  return infix;
}

打怪升级

再来看一道题,这道题是 2020 年 9 月 6 日字节笔试的第二题。难度对标 leetcode 的 medium 级别。

给定一个长为 n 的序列 a。L[i] 表示第 i 个位置左边第一个大于 a[i] 的数的下标(从 1 开始),没有的话为 L[i] = 0。R[i] 表示第 i 个位置右边第一个大于 a[i] 的数的下标(从 1 开始),没有的话为 R[i] = 0。求

思路分析:一看题目,就是单调栈的第一种用法。使用两次单调栈分别得到 L[i] 和 R[i],再遍历一遍即可。时间复杂度为 O(n)。

代码如下:

public int solve(int[] a){
  if(a == null) throw new RuntimeException("输入有误!"); //细节,一定要细
  int n = a.length;
  int[] L = new int[n], R = new int[n];
  // 这里分两次 for 循环来写,熟练的话可以放在同一个 for 循环里。
  Stack<Pair> stack = new Stack();
  for(int i = 0; i < n; i++){
    while(!stack.isEmpty() && stack.peek().val < a[i]) stack.pop();
    L[i] = stack.isEmpty() ? 0 : stack.peek().id + 1; //注意题目要求下标是从 1 开始的
    stack.push(new Pair(i, a[i]));
  }
  stack.clear();
  for(int i = n - 1; i >= 0; i--){
    while(!stack.isEmpty() && stack.peek().val < a[i]) stack.pop();
    R[i] = stack.isEmpty() ? 0 : stack.peek().id + 1; //注意题目要求下标是从 1 开始的
    stack.push(new Pair(i, a[i]));
  }
  // L[i] 和 R[i] 计算完毕,下面遍历一遍得到最大值即可
  int ans = 0;
  for(int i = 0; i < n; i++) ans = Math.max(ans, L[i] * R[i]);
  return ans;
}

class Pair{
  int id; // 下标
  int val;
  public Pair(int id, int val){
    this.id = id;
    this.val = val;
  }
}

出师试炼

关卡 1

给定一个整数数组,你需要验证它是否是一个二叉搜索树正确的先序遍历序列。

你可以假定该序列中的数都是不相同的。

关卡 2

给定一个以字符串表示的非负整数 num*,移除这个数中的 *k 位数字,使得剩下的数字最小。

关卡 3

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,能够勾勒出来的矩形的最大面积。

PS:在公众号【往西汪】后台回复关键字【单调栈】,即可获得上述关卡的过关秘籍(代码实现)。

本期单调栈问题就分享到这,下一期你想看什么内容呢?单调队列?前缀和思想?还是老汪独家刷题秘籍?又或者有其他想看的,也可以在下方评论区告诉老汪。

我是往西汪,致力于面向 offer 分享算法知识,希望你早日收获心仪 offer。我们下期再见。

喜欢就点赞哦

全部评论

(2) 回帖
加载中...
话题 回帖

相关热帖

近期热帖

近期精华帖

热门推荐