目录

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

前言

枯燥栈是一种比拟 简略 的数据结构。尽管简略，但在某些题目中能施展很好的作用。

最近很多 大厂的口试、面试中 都呈现了枯燥栈的题目，而还有不少小伙伴连枯燥栈是什么都不理解，因而老汪专门写了这篇文章，心愿对你们有所帮忙。

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

给定一个二叉搜寻树，并给出他的前序序列，要求输入中序序列，工夫复杂度 O(n)，并给出证实。

枯燥栈

• 是什么：枯燥栈是一种 具备枯燥性的栈 ，任何时刻 从栈顶到栈底 的元素都是 枯燥增 / 减 的。

• 干什么：

  • 枯燥栈能够找到从 左 / 右 遍历 第一个 比它 大 / 小 的元素的地位。
  • 枯燥栈也能够将某个元素 左 / 右 边所有比它 小 / 大 的元素按 升 / 降序 输入。
• 怎么做：应用栈构造，在入栈的时候放弃 id 和 val 的枯燥性即可。

翻译成大白话，但凡遇到题目中 间接或间接 要求 查找某个元素左 / 左边第一个大于 / 小于它的元素 ，或者要求 将某个元素左 / 左边所有小 / 大于它的元素按升 / 降序输入，就能够应用枯燥栈来解决。

具体怎么做你可能还有些迷糊，上面咱们间接通过做题来加深对枯燥栈的了解。十分钟包教包会，当天就能够和面试官对线。

初入茅庐

给定数组 a，要求输入这样的数组 b，b[i] 是 a[i] 右边第一个比 b[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] 大的元素
    if(stack.isEmpty()) stack.push(a[i]);
    b[i] = stack.peek();}
  return b;
}

这代码也是枯燥栈问题的 根本构造，所有枯燥栈问题的代码都基于此进行变种、扩大。小伙伴们能够多花两分钟好好消化下面的代码。

思考到有些小伙伴不必 Java，老汪把上述代码形象成伪代码，这也是 枯燥栈的根本构造。

背诵 + 套用，即可解决所有枯燥栈问题。

函数 solve (数组 a):
    新建数组 b;
    新建栈 stack;
    For i From 0 To n - 1:
        While 栈非空 且 栈顶元素 < a[i]：出栈;
        End While
        If 栈空 Then:
            a[i] 入栈;
        End If
        b[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。求 $max_{i = 1}^{n}L[i]·R[i]$。

思路剖析：一看题目，就是枯燥栈的第一种用法。应用两次枯燥栈别离失去 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。咱们下期再见。