目錄

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，求 $ma{x}_{i=1}^{n}L[i]?R[i]$maxi=1n?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，我們下期再見，