01栈：从简单栈到单调栈，解决经典栈问题

今天我们开始学习一个在工作，以及面试中经常被问到的一个数据结构——栈。

栈这种数据结构，在计算机中有着广泛地运用，比如编程语言中函数的调用、操作系统中从用户态到内核态寄存器的保存、网络消息的处理等都会用到栈。

今天我们主要介绍面试中经常考察的栈相关的高频题目，主要内容包含两方面：

栈的特性与使用

单调栈的解题技巧

针对一道题目，我会深度讲解一种解法，以及其变型，并且带你总结同类问题的解题技巧和规律，从而解决多种相似及变形题目。并且，我会给出 Java/C++/Python 三种代码示例，方便你学习。现在，开始我们的旅程与探险！

栈的特性与使用

简单栈的特点可以用一句话来概括，先进后出（LIFO）顺序。比如 Java 代码（解析在注释里）：

1
2
3
4
5
6
7


Stack<Character> t = new Stack<Character>();
t.push('a');
t.push('b');
t.peek(); // 这里得到栈顶元素'b'
t.pop();  // 这里将栈顶元素'b'弹出
t.peek(); // 此时栈顶元素为'a'
t.pop();  // 这里将栈顶元素'a'弹出

这部分代码片段执行效果如下图所示：

那么如何深度利用栈的“先进后出”特点来解决实际工作和面试中的问题呢？是否可以总结出什么有用的知识技巧？现在你的大脑里可能已经有了一个栈的“萌芽”，如下图所示：

接下来我将通过大厂面试题，带你学习这块重点知识。经过不断地“浇灌”，栈这棵“萌芽”才能抽枝散叶，长得更加茁壮。

例 1：判断字符串括号是否合法

【题目】字符串中只有字符’(‘和’)’。合法字符串需要括号可以配对。比如：

输入："()"

输出：true

解释：()，()()，(())是合法的。)(，()(，(()是非法的。

请你实现一个函数，来判断给定的字符串是否合法。

1

boolean isValid(String s);

【分析】虽然这是一道简单题，但是我们依然可以拿它来训练深度思考的能力。如果你已经知道答案，或者说能够轻松地解决这道题，不妨再跟我一起看看如何拆解这道题。

首先，分析题目的时候，要特别注意以下 4 点，归纳为“四步分析法”。

模拟：模拟题目的运行。

规律：尝试总结出题目的一般规律和特点。

匹配：找到符合这些特点的数据结构与算法。

边界：考虑特殊情况。

接下来我们就按照上面的步骤来拆解题目。

1. 模拟

首先我们以字符串 s = “()()(())"，进行模拟，如下动图所示：

2. 规律

我们回顾一下模拟过程，可以总结出以下 3 个特点。

（1）每个左括号’(‘或者右括号’)‘都完成配对，才是合法的。

（2）配对可以通过消除法来消掉合法的括号，如果最后没有任何字符了，那么就是合法字符串。

（3）奇数长度的字符串总是非法的。

3. 匹配

到这里，我们已经弄清楚题目考核的重点，就是消除法的模拟。如果仔细观察消除法的行为模式，你会发现，在消除的时候，上图中红色的部分和栈的行为非常像。因此，可以用栈来进行消除法的模拟。

4. 边界

当我们找到问题匹配的算法或者数据结构之后，一定要记住，接下来一步并不是马上写代码，而是要考虑一些边界问题，也就是一些特殊情况：

字符串为空

字符串只有 1 个或者奇数个

字符串是”(((())))“嵌套很多层的是否可以处理

【画图】可以采用画图的方法来判断自己是否已经了解题目，或者是否能灵活运用一个算法。在面试中经常需要在白板或者纸上画图，所以在学习算法时候建议你培养多画图的习惯。

当遇到左括号’(‘时，进行压栈操作

当遇到右括号’)‘时，进行弹栈操作

为了帮助你更好地理解，我将求解过程制作成一张动图，如下所示，注意左边栈的变化。

【代码】到这里时，你可以写出以下核心代码（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


boolean isValid(String s) {
  // 当字符串本来就是空的时候，我们可以快速返回true
  if (s == null || s.length() == 0) {
    return true;
  }
  // 当字符串长度为奇数的时候，不可能是一个有效的合法字符串
  if (s.length() % 2 == 1) {
    return false;
  }
  // 消除法的主要核心逻辑: 
  Stack<Character> t = new Stack<Character>();
  for (int i = 0; i < s.length(); i++) {
    // 取出字符
    char c = s.charAt(i);
    if (c == '(') {
      // 如果是'('，那么压栈
      t.push(c);
    } else if (c == ')') {
      // 如果是')'，那么就尝试弹栈
      if (t.empty()) {
        // 如果弹栈失败，那么返回false
        return false;
      }
      t.pop();
    }

  return t.empty();
}

代码：Java,C++,Python

复杂度分析：每个字符只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况下可能会把整个字符串都入栈。

做完一道题后，我们还需要从两个角度进行深度思考：

深度，比如这种解法还可以怎么优化呢？

广度，比如这种解法具有普适性吗？可以推广吗？

1. 深度扩展

如果仔细观察，你会发现，栈中存放的元素是一样的。全部都是左括号’(’，除此之外，再也没有别的元素，优化方法如下。

栈中元素都相同时，实际上没有必要使用栈，只需要记录栈中元素个数。我们可以通过画图来解决这个问题，如下动图所示：

实际上，就是把入栈与出栈变成了 leftBraceNumber 的加减。代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28


public boolean isValid(String s) {
  // 当字符串本来就是空的时候，我们可以快速返回true
  if (s == null || s.length() == 0) {
    return true;
  }
  // 当字符串长度为奇数的时候，不可能是一个有效的合法字符串
  if (s.length() % 2 == 1) {
    return false;
  }
  // 消除法的主要核心逻辑:
  int leftBraceNumber = 0;
  for (int i = 0; i < s.length(); i++) {
    // 取出字符
    char c = s.charAt(i);
    if (c == '(') {
      // 如果是'('，那么压栈
      leftBraceNumber++;
    } else if (c == ')') {
      // 如果是')'，那么就尝试弹栈
      if (leftBraceNumber <= 0) {
        // 如果弹栈失败，那么返回false
        return false;
      }
      --leftBraceNumber;
    }
  }
  return leftBraceNumber == 0;
}

代码：Java,C++,Python

复杂度分析：每个字符只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(1)，因为我们已经只用一个变量来记录栈中的内容。

【小结】经过前面的分析，现在我们可以将题目的特点做一下小结：

2. 广度扩展

接下来再来看看如何进行广度扩展。观察题目可以发现，栈中只存放了一个维度的信息：左括号’(‘和右括号’)’。如果栈中的内容变得更加丰富一点，就可以得到下面这道扩展题。

【题目扩展】给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。有效字符串需满足：

左括号必须用相同类型的右括号闭合

左括号必须以正确的顺序闭合

注意空字符串可被认为是有效字符串

请实现接口： public boolean isValid(String s)

对于这道题，我希望你能再走一下：分析，画图，代码，扩展，小结的五步曲。

代码：Java,C++,Python

【小结】接下来，我们对拓展题目进行总结，希望你从中提炼出经验，以后再遇到相似的题目能够轻松应对。

对于栈的使用，除了知道“后进先出”这个规律，我们还可以帮它长出一些叶子来，如下图所示：

因此，以后你在看到题目中类似配对、消除之类的动作时，可以采用栈来操作。通过这两个方向上的整理和归纳，我们进一步探寻到了题目和解法之间的联系。让我们继续前进。

例 2：大鱼吃小鱼

【题目】在水中有许多鱼，可以认为这些鱼停放在 x 轴上。再给定两个数组 Size，Dir，Size[i] 表示第 i 条鱼的大小，Dir[i] 表示鱼的方向（0 表示向左游，1 表示向右游）。这两个数组分别表示鱼的大小和游动的方向，并且两个数组的长度相等。鱼的行为符合以下几个条件:

所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离；

当方向相对时，大鱼会吃掉小鱼；

鱼的大小都不一样。

输入：Size = [4, 2, 5, 3, 1], Dir = [1, 1, 0, 0, 0]

输出：3

请完成以下接口来计算还剩下几条鱼？

1

int solution(int[] Size, int[] Dir);

题目的示意图如下所示：

【分析】对于这道题而言，大鱼吃掉小鱼的时候，可以认为是一种消除行为。只不过与括号匹配时的行为不一样：

括号匹配是会同时把左括号与右括号消除掉；

大鱼吃小鱼，只会把小鱼消除掉。

1. 模拟

首先我们以如下示例进行演示：

1

Size = [4, 3, 2, 1 5], Dir = [0, 1, 0, 0, 0]

注意：当鱼的游动方向相同，或者相反时，并不会相遇，此时大鱼不能吃掉小鱼。

2. 规律

通过模拟，可以发现如下规律:

如果两条鱼相对而游时，那么较小的鱼会被吃掉；

其他情况没有鱼被吃掉。

3. 匹配

我们发现，下面活下来的鱼的行为（上图红框部分）就是一个栈。每当有新的鱼要进来的时候，就会与栈顶的鱼进行比较。那么我们匹配到的算法就是栈了。

4. 边界

在正式开始求解之前，我们还是想一想两种边界：

所有的鱼都朝着一个方向游；

一条鱼吃掉了其他的所有鱼。

我们在后面设计算法的时候，这些情况都需要考虑到。

【画图】这道题的关键仍然是如何使用栈来模拟鱼的消除行为。接下来我们用栈画一下图，演示出我们的思路，动图如下：

【代码】根据之前的思考，可以得到如下解法（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36


int solution(int[] fishSize, int[] fishDirection) {
  // 首先拿到鱼的数量
  // 如果鱼的数量小于等于1，那么直接返回鱼的数量
  final int fishNumber = fishSize.length;
  if (fishNumber <= 1) {
    return fishNumber;
  }
  // 0表示鱼向左游
  final int left = 0;
  // 1表示鱼向右游
  final int right = 1;
  Stack<Integer> t = new Stack();
  for (int i = 0; i < fishNumber; i++) {
    // 当前鱼的情况：1，游动的方向；2，大小
    final int curFishDirection = fishDirection[i];
    final int curFishSize = fishSize[i];
    // 当前的鱼是否被栈中的鱼吃掉了
    boolean hasEat = false;
    // 如果栈中还有鱼，并且栈中鱼向右，当前的鱼向左游，那么就会有相遇的可能性
    while (!t.empty() && fishDirection[t.peek()] == right &&
           curFishDirection == left) {
      // 如果栈顶的鱼比较大，那么把新来的吃掉
      if (fishSize[t.peek()] > curFishSize) {
        hasEat = true;
        break;
      }
      // 如果栈中的鱼较小，那么会把栈中的鱼吃掉，栈中的鱼被消除，所以需要弹栈。
      t.pop();
    }
    // 如果新来的鱼，没有被吃掉，那么压入栈中。
    if (!hasEat) {
      t.push(i);
    }
  }
  return t.size();
}

代码：Java,C++,Python

复杂度分析：每只鱼只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况下可能把所有的鱼都入栈。

【小结】接下来我们一起对这道题做一下归纳。可以发现，与例 1 相比，它们的消除行为有所不同：

在例 1 中，消除行为表现为配对的两者都会消除；

在例 2 中，消除行为表现为配对的两者中有一个会被消除。

此外，在与例 1 的比较中，可以发现，栈中的内容也有所不同：

在例 1 中，栈中的存放的就是内容本身；

在例 2 中，栈中存放的只是内容的索引，可以通过索引得到内容。

再者，我们也发现，在弹栈的时候，不再像以前那样，每次只弹一个元素，而是采用了 while 循环，要一直弹到满足某个条件为止。所以我们总结出，弹栈的时候有两种情况：

弹一个元素就可以；

用 while 语句一直弹，直到满足某个条件为止。

因此，这道题的考点我们也挖掘出来了：

是否会用栈来存放索引？

是否想到在弹栈的时候一定要满足某个条件才停止弹栈？

到这里栈的特点更丰富了，通过我们不断地浇灌也让栈这棵“萌芽”长出了更多的叶子，总结如下图所示：

单调栈的解题技巧

大部分数据结构书上都不太会讲单调栈的知识，但是在面试中却经常考察这一类题，这就非常考验你的知识储备了。

首先我们看一下单调栈的定义：单调栈就是指栈中的元素必须是按照升序排列的栈，或者是降序排列的栈。对于这两种排序方式的栈，还给它们各自取了小名。

升序排列的栈称为递增栈，如下图所示：

降序排列的栈称为递减栈，如下图所示：

注意：示意图所展示的这两种栈是横向排列的。栈中元素的值，分别用不同高度的矩形来表示，值越大，矩形越高。

接下来我们介绍一下递增栈的有序性，一句话：“任何时候都需要保证栈的有序性”。

递增栈的特性可以演示如下（上方数组是要依次入栈的元素）：

递减栈的特性可以演示如下：

通过这两个动图，我们可以总结出单调栈的特点，如下图所示：

接下来我们通过一些小题目来对单调栈进行“浇灌”，也让单调栈长出更多的“叶子”。

例 3：找出数组中右边比我小的元素

【题目】一个整数数组 A，找到每个元素：右边第一个比我小的下标位置，没有则用 -1 表示。

输入：[5, 2]

输出：[1, -1]

解释：因为元素 5 的右边离我最近且比我小的位置应该是 A[1]，最后一个元素 2 右边没有比 2 小的元素，所以应该输出 -1。

1

接口：int[] findRightSmall(int[] A);

【分析】每次开始分析题意时，记得要拿出我们的“四步分析法”，通过一步步分析找到题目相应的解法。

1. 模拟

在正式开始上手之后，我们先拿两个例子演示一下，看看能不能发现题目中隐藏的一些有趣规律，动图如下所示：

2. 规律

这里我们是照着题意去寻找一个右边比它小的数的下标。可以发现，A[4] = 4 及 A[5] = 0，这两个数字多次被用到。并且：

A[4] 发现有左边 A[3]，A[3] 就匹配成功；

结合 A[5] = 0 的例子，我们发现它会把比它大的数都进行匹配成功，但是 A[3] 除外；

A[3] 可以认为是匹配成功之后，被 A[4]消除了。

这时可以总结出：一个数总是想与左边比它大的数进行匹配，匹配到了之后，小的数会消除掉大的数。

3. 匹配

当你发现要解决的题目有两个特点：

小的数要与大的数配对

小的数会消除大的数

你的脑海里应该联想到关于单调栈的特性。下面我们看看如何利用单调栈解决这道题目。

【画图】在这里，依然需要画一个图来描述一下我们的思路及想法，如下图所示：（红色部分表示栈，我们只将下标绿色值放到栈中，为了看图方便，把下标对应的值也标在了相应位置。）

Step 1. 首先将 A[0] = 1 的下标 0 入栈。

Step 2. 将 A[1] = 2 的下标 1 入栈。满足单调栈。

Step 3. 将 A[2] = 4 的下标 2 入栈。满足单调栈。

Step 4. 将 A[3] = 9 的下标 3 入栈。满足单调栈。

Step 5. 将 A[4] = 4 的下标 4 入栈时，不满足单调性，需要将 A[3] = 9 从栈中弹出去。下标 4 将栈中下标 3 弹出栈，记录 A[3] 右边更小的是 index = 4。

Step 6. 将 A[5] = 0 的下标 5 入栈时，不满足单调性，需要将 A[4] = 4 从栈中弹出去。下标 5 将下标 4 弹出栈，记录 A[4] 右边更小的是 index = 5。A[5] = 0 会将栈中的下标 0, 1, 2 都弹出栈，因此也需要记录相应下标右边比其小的下标为 5，再将 A[5] = 0 的下标 5 放入栈中。

Step 7. 将 A[6] = 5 的下标 6 放入栈中。满足单调性。

Step 8. 此时，再也没有元素要入栈了，那么栈中的元素右边没有比其更小的元素。因此设置为 -1.

【代码】到此为止，相信你已经可以根据思路写出代码了，代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


public static int[] findRightSmall(int[] A) {
  // 结果数组
  int[] ans = new int[A.length];
  // 注意，栈中的元素记录的是下标
  Stack<Integer> t = new Stack();
  for (int i = 0; i < A.length; i++) {
    final int x = A[i];
    // 每个元素都向左遍历栈中的元素完成消除动作
    while (!t.empty() && A[t.peek()] > x) {
      // 消除的时候，记录一下被谁消除了
      ans[t.peek()] = i;
      // 消除时候，值更大的需要从栈中消失
      t.pop();
    }
    // 剩下的入栈
    t.push(i);
  }
  // 栈中剩下的元素，由于没有人能消除他们，因此，只能将结果设置为-1。
  while (!t.empty()) {
    ans[t.peek()] = -1;
    t.pop();
  }
  return ans;
}

代码：Java,C++,Python

复杂度分析：每个元素只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况可能会把所有的元素都入栈。

【小结】到这里我们可以得到一个有趣且非常有用的结论：数组中右边第一个比我小的元素的位置，求解用递增栈。

这里给你留几道练习题，请你思考如何求解。

数组中右边第一个比我大的元素的位置

代码：Java/C++/Python

数组中元素左边离我最近且比我小的元素的位置

代码：Java/C++/Python

数组中元素左边离我最近且比我大的元素的位置

代码：Java/C++/Python

如果我们进一步归纳，会发现消除的时候，这里仍然是消除一个元素，保留一个元素。弹栈的时候，仍然是一直弹栈，直到满足某个条件为止。只是条件变成了直到元素大于栈顶元素。为了方便你理解，我把内容总结到了一张大图里：

例 4：字典序最小的 k 个数的子序列

【题目】给定一个正整数数组和 k，要求依次取出 k 个数，输出其中数组的一个子序列，需要满足：1. 长度为 k；2.字典序最小。

输入：nums = [3,5,2,6], k = 2输出：[2,6]

解释：在所有可能的解：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 字典序最小。

所谓字典序就是，给定两个数组：x = [x1,x2,x3,x4]，y = [y1,y2,y3,y4]，如果 0 ≤ p < i，xp == yp 且 xi < yi，那么我们认为 x 的字典序小于 y。

1

接口：int[] findSmallSeq(int[] A, int k);

【分析】根据“四步分析法”，我们一步一步拆解题目。

1. 模拟

首先应该拿例子来模拟一下题目所述的过程，动图如下所示：

2. 规律

通过模拟，我们发现一个特点：一旦发现更小的数时，就可以把前面已经放好的数扔掉，然后把这个最小的数放在最前面。

如果机智一点，就会发现这里与例 2 的“大鱼吃小鱼”结果很像。区别在于消除的过程中，大鱼吃小鱼是大鱼留下来了，而这里较小的数和较大的数相遇时，是较小的数留下来了。

3. 匹配

到这里，我们已经发现了题目的特点——较小数消除掉较大数。根据例 3 总结出来的规律，此时就可以用上单调栈。并且，由于是较小的数消除掉较大的数，所以应该使用递增栈。

4. 边界

不过我们还是需要小心题目的边界。

Case 1：假设数组右边有一个最小的数，这个最小的数会把左边的数全部都消掉，然后递增栈里面就只剩下这 1 个数了。这跟题意有点不符合，题意需要的是找到 k = 2 个出来。

解决办法：不过你可以想一想，是不是可以控制一下消去的数目。当剩下的数字个数与栈中的元素刚好能凑够 k 个数时，就不能再消除了，代码如下 :

1

rightLeftNumber + stack.size() == k

此时，如果还要进行消除，就不能凑够 k 个数了。这样操作可以保证我们取的序列是最小的 k 个数。

Case 2：如果数组是一个升序的数组，那么此时所有的元素都会被压栈。栈中的数目有可能远远超出 k 个。

解决办法：只需要把栈中的多出来的数字弹出来即可。

【画图】假定输入为[9, 2, 4, 5, 1, 2, 3, 0], k = 3.输出能构成的最小的序列。

Step 1. 首先将 9 加入栈中。

Step 2. 当 2 要入栈时，不满足单调栈，需要将数字 9 出栈。由于后面还有足够多的元素，可以把 9 弹栈，再将 2 入栈。

Step 3. 将 4 入栈，满足单调性。

Step 4. 再将元素 5 入栈，满足单调性。

Step 5. 将要入栈的元素 1，会弹出栈中所有元素。

Step 6. 将元素 1 入栈。

Step 7. 将元素 2 入栈，满足单调性。

Step 8. 将元素 3 入栈，满足单调性。

Step 9. 将 0 入栈时，需要将栈顶元素 3 弹出。

Step 10. 将 0 入栈，不满足单调性。这是因为，如果 0 将前面的元素再弹栈，余下的元素个数就小于 k = 3 个了。所以不能再利用单调性来弹出栈中元素了。

【代码】到这里，相信你已经可以根据思路写出代码了，代码如下（解析在注释里）：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


public int[] findSmallSeq(int[] nums, int k) {
  int[] ans = new int[k];
  Stack<Integer> s = new Stack();
  // 这里生成单调栈
  for (int i = 0; i < nums.length; i++) {
    final int x = nums[i];
    final int left = nums.length - i;
    // 注意我们想要提取出k个数，所以注意控制扔掉的数的个数
    while (!s.empty() && (s.size() + left > k) && s.peek() > x) {
      s.pop();
    }
    s.push(x);
  }
  // 如果递增栈里面的数太多，那么我们只需要取出前k个就可以了。
  // 多余的栈中的元素需要扔掉。
  while (s.size() > k) {
    s.pop();
  }
  // 把k个元素取出来，注意这里取的顺序!
  for (int i = k - 1; i >= 0; i--) {
    ans[i] = s.peek();
    s.pop();
  }
  return ans;
}

代码：Java,C++,Python

复杂度分析：每个元素只入栈一次，出栈一次，所以时间复杂度为 O(N)，而空间复杂度为 O(N)，因为最差情况可能会把所有元素都入栈。

【小结】写完代码之后，我们需要对代码和题目做一个小结：

较小的数消除掉较大的数的时候，使用递增栈；

要注意控制剩下的元素的个数；

如果更进一步推而广之，会发现从简单栈到单调栈，层层推进的过程中，不停变化就是入栈与出栈的时机。

那么，到这里，这个题目的考点也就非常明了了：

递增栈

个数控制，我们只需要取 k 个数出来。

总结与延伸

在本讲我带你一起剖析了栈相关的知识和题目，经过我们不断地“浇灌”，栈这棵“萌芽”开始抽枝散叶，终于长成了一棵枝繁叶茂的“大树”。回到知识层面，我把本讲重点介绍、且需要你掌握的内容总结在一张思维导图中，如下图所示：

除了带你学习知识本身，我还介绍了题目的变形和演进，希望能够帮助你建立深度分析的能力。在学习算法与数据结构的过程中，作为“刷题过来人”，我非常建议你加强总结和归纳，建立自己的学习方法论。

虽然栈很有趣，不过我们的介绍就要到这里了，我对于栈的总结和归纳只是个开头，期待你还能发现更多栈的特点和巧妙用法，并且将它们总结下来。也欢迎在评论区和我交流，期待看到你的奇思妙想。

思考题

我再给你留一道思考题：给定一个数组，数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积。

这道题会涉及一个非常重要且有用的单调栈的性质，希望你能找到它。你可以把答案写在评论区，我们一起讨论。

解法 1：Java/C++/Python解法 2：Java/C++/Python

接下来请和我一起踏上更加奇妙的算法与数据结构的旅程。让我们继续前进。下一讲将介绍 02 | 队列：FIFO 队列与单调队列的深挖与扩展，记得按时来探险。

-– ### 精选评论 ##### **龙： > 老师你好愿风指引你的道路我想问下老师像我这种半路的程序员数学基础不太好的有什么书或者资料能推荐推荐的吗？谢谢老师了 ###### 讲师回复： > 我把这个问题分为两部分：1. 程序员的基本功。2. 数学部分这个没有太多的捷径。你需要静下心来一步一步啃。首先说，程序员的基本功。a. 数据结构和算法，数据结构可以看一下严蔚敏的<数据结构>，算法的话，可以看<算法4>。注意，看书的时候，注意刷题。比如看了链表，就尝试把最简单的链表tag题刷掉。学一章节，刷一章节的内容。刷完一定要总结自己的代码模板。一定要总结，一定要总结！！。你也可以跟着本专栏把问题一个一个搞明白，从头到尾看完，再回过头去看书的话，可能看起来感觉会不太一样。书毕竟是经验的总结。你有过一定的实操之后，再去看经验，可能感悟会不太一样。然后是数学部分。我个人觉得离散数学大部分时候都够用了。后续可以看概率（不需要看很难的那种）最后是内功部分，数据结构和算法我已经说过了。那么余下的就是操作系统，网络，数据库。这四块决定了你的职业天花板。 ##### *斌： > 最好也能给出leetcode 相对应的题，以便联系 ###### 讲师回复： > 点开每个题的代码：Java/C++/Python的那个链接。在每一个题的git repo里面的链接，完整的代码，以及相应的测试平台或者leetcode 链接都是有的。比如：https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/03.HeapAndPriorityQueue/1642.可以到达的最远建筑.java 在注释部分。就有相关的测试平台的链接。 ##### **6400： > 老师，大鱼吃小鱼的题里，这个条件是不是没有用到?【所有的鱼都同时开始游动，每次按照鱼的方向，都游动一个单位距离】 ###### 讲师回复： > 这个条件的作用是保证：相同方向的鱼在游动的时候，永远不会相遇。比如一条小鱼向左游动，它的后面有一条大鱼也是向左游动。由于有这个条件的限制，那么后面的大鱼是追不上前面的小鱼的。通过这种方式，问题可以得到简化。否则后面的大鱼追上来也可以吃掉小鱼，问题就不太一样了。 ##### *洪： > 感觉这才是学栈，以前就知道先进后出😂😂😂 ##### **5467： > 咋没有javascript版本的😂 ###### 讲师回复： > 由于时间限制，先支持Java/C++/Python三种语言，专栏完成之后，我再根据大家的需求反馈添加其他的语言。如果有其他问题，也欢迎你继续提问～ ##### **鹏： > 字典序最小:直白的理解就类似查字典，那就要从前往后遍历，如两个字符串或两个数组比较，第一个最小的那个字符串或数组为字典序最小，如果第一个相同就比较第二个，依次类推，得出字典最小的那个字符串或数组。我粗俗的解释😉 ###### 编辑回复： > 给你点个赞！ ##### **其： > 老师，关于栈的思考题：给定一个数组，数组中的元素代表木板的高度。请你求出相邻木板能剪出的最大矩形面积。我觉得此题给出的解法做的不是很好。存在一些问题，1、解法一的核心是穷举法，子问题才是单调栈；在此作为栈的单一课程学员解决问题时还需要储备课程外知识。2、两个解法中都没有按照课程给出的解题流程解题，而是突兀的提出了解题方式，对于解法一来说还容易理解一点，但是解法二直接就是性质一性质二，这两个性质如何得出的为什么能解决问题没有说明，我比较愚钝，没能理解解法二到底说了什么。 ###### 讲师回复： > 关于思考题，目前代码只是直接给出了答案，后续我会把解法二的两个性质详细讲解，并将每一讲的习题答案放在专栏加餐内容中。大家有什么疑问，也可以留言告诉我，我会根据留言反馈增设加餐内容， ##### **珠： > 老师，这个时间和空间复杂度一直没搞懂是怎么计算的？时间复杂度为 O(N)，而空间复杂度为 O(N) ###### 讲师回复： > 首先我们看空间复杂度：这个就是看你的栈申请了多少空间。比如最差的时候，有多少个元素在栈里面。那么这个就是你的空间复杂度。关于时间复杂度，对于栈和队列我有一个比较巧妙的办法就是：只看单个元素的入栈次数，出栈栈次数。如果每个元素都是只是入栈一次，出栈一次，那实际上就是相当于每个元素访问了一遍。所以就是O(N) 你可能会想，啊，一个元素入栈的时候，不是还会把很多元素弹栈么？但是这个只是把入栈的顺序打乱了。比如当单调栈，A要入栈时，要把BC两个元素弹栈。以前是A进,B进,C进,C弹,B弹,A弹。=> 现在变成了B进C进C弹B弹A进A弹。只是换了一种排列组合而已，时间复杂度并没有变。 ##### **鹏： > 这也太硬核了吧…1元竟然上车了😂 ##### **蕾： > // case3_03 : 找出左边第一个比我小的数func case3_03(nums []int) []int { if len(nums) == 0 { return []int{} } if len(nums) == 1 { return []int{-1} } results := make([]int, len(nums)) _stack := list.New() for i := len(results) - 1; i “>1; i– { for _stack.Len() “>0 { _last := _stack.Back().Value.(int) if nums[_last] nums[i] { results[_last] = i } else { break } _stack.Remove(_stack.Back()) } _stack.PushBack(i) } for e := _stack.Front(); e != nil; e = e.Next() { idx := e.Value.(int) results[idx] = -1 } return results}// case3_04 : 找出左边第一个比我大的数func case3_04(nums []int) []int { if len(nums) == 0 { return []int{} } if len(nums) == 1 { return []int{-1} } results := make([]int, len(nums)) _stack := list.New() for i := len(results) - 1; i “>1; i– { for _stack.Len() “>0 { _last := _stack.Back().Value.(int) if nums[_last] nums[i] { results[_last] = i } else { break } _stack.Remove(_stack.Back()) } _stack.PushBack(i) } for e := _stack.Front(); e != nil; e = e.Next() { idx := e.Value.(int) results[idx] = -1 } return results} ##### lgt： > 【题目】给定一个正整数数组和 k，要求依次取出 k 个数，输出其中最小的 k 个。输入：nums = [3,5,2,6], k = 2输出：[2,6]解释：在所有可能的解：{[3,5], [3,2], [3,6], [5,2], [5,6], [2,6]} 中，[2,6] 最小请问这个为什么不是[3,2]最小 ###### 编辑回复： > 不好意思，原来文章中的表述并不清晰，现在用更加严谨一点的语言来描述。已经重新更新。如有什么疑问，我们再交流 ##### **宁： > 老师问下，您这个GIF效果拿啥公工具制作的，很好很强大 ###### 编辑回复： > 用得是PPT+draw.io哦 ##### **涛： > 赞，太棒了 ##### *中： > 例4 题没读懂 ###### 讲师回复： > 首先看一个简单的例子我们用>表示向右，<表示向左游。 Case 1. 假设有两条鱼，向着同样的方向游。比如 3>, 5> 一起向右游动。这个时候，大鱼是吃不了小鱼的因为他们总是向一个方向游。并且速度一样。鱼也不能换方向。 Case 2: 假设有两条鱼，<3, 5> 这个时候，大鱼仍然吃不了小鱼。因为他们是照相反方向游动的。 Case 3: 假设有两条鱼。3> <5 这下他们相向而游，大鱼一定会把小鱼吃掉。所以最后只会有<5留下来。 Case 4: 假设有3条鱼，3> 5> <4 首先碰面的是5> <4, size=5的鱼会把size=4的鱼吃掉。情况就退化成为 3> 5> 所以这种情况，还会有3> 5>留下来。虽然3是最小的。 ##### *政： > 大鱼吃小鱼如果两条鱼一样大，但是方向不同的情况是不是有点问题，会被吃掉 ###### 讲师回复： > 题目有条件：鱼的大小都不一样。也就是没有一样大的鱼 ##### **皆可花椒油： > 用什么做的动画啊，很形象啊，赞 ###### 编辑回复： > 感谢小伙伴的认可，用的是draw.io+PPT哦 ##### **辛： > 那三道练习题老师有没有答案讲解 ###### 编辑回复： > 关于练习题，如有问题可以先在留言区提问。老师看到大家的强烈呼声，已经在准备练习题的详细解答了，届时会作为加餐更新哦 ##### **7823： > 大鱼吃小鱼的代码，结果栈 t 初始化是空栈，后面的 while 循环条件 len(t) 要大于 0，这个循环进不去吧 ###### 讲师回复： > 首先，当第一条鱼进来的时候，确实是进不去 while (!t.empty() && fishDirection[t.peek()] == right && curFishDirection == left) 的。因为此时栈是空的。接下来，第一条鱼会走到 hasEat = false; (因为只有在这个while循环里面才会被修改hasEat) 所以接下来会走到 if (!hasEat) { t.push(i); } 此时栈中就有鱼了。那么后面的鱼接下来就会根据情况来做判断了。 ##### **帆： > 两的很好，还是希望老师能给出没每道题的leetcode的序号或者地址，毕竟国内最近github访问不是很流程 ###### 编辑回复： > 好哦，小伙伴的建议我们收到了！后面老师会给大家把题号标注出来哈 ##### *莹： > 老师，请问相邻只是指两两相邻，还是多个两两相邻 ###### 讲师回复： > 这里的意思是说，你必须使用连在一起的木板来切出一个大的长方形。比如，给定数组A= [1000, 1, 1000] 在拼长方形的时候，你可以A[0], A[1]一起。A[1], A[2]一起。或者A[0], A[1], A[2]一起。因为你挑出来的都是相临的。但是，你不能A[0], A[2]在一起。因为这两个并不挨着的。简单地说，就是必须要连续的子数组 ##### **豪： > 打鱼吃小鱼的题，假如大小为3、5的鱼向右游，大小为4的鱼向左游，怎么能保证4能吃到3呢？ ###### 讲师回复： > 我们假设>表示向右游，<表示向左游 3，5 > <4 size=5的鱼游动过去的时候，肯定会把size=4的鱼吃掉。所以最终栈中只有3, 5>。也就是说，size=4的鱼，是无法吃掉size=3的鱼的 ##### Ivan： > 你好，方便列一下这几道题的复杂度么 ###### 编辑回复： > 谢谢小伙伴的反馈，老师已经在文章中补充了四道例题的复杂度分析，可以去看一下哈。 ##### **键： > public static int findXY(int[] array) { int a = 0; for (int i = 1; i “>length - 1; i++) { int befor = array[i - 1]; int current = array[i]; int after = array[i + 1]; int min = current “>; min = min “>; a = a “>; } return a * 3;} ##### **莹： > 太可以了吧，非常清晰啊 ##### **明： > 老师你好，请问大鱼吃小鱼例子里面，为什么栈中鱼是否向右用fishDirection[t.peek()] == right 来判断？t.peek好像是返回栈顶的元素，比如栈顶是5，那fishDirection[5]不就是取第5个元素了吗，感觉应该是取fishDirection[5对应的索引]？ ###### 讲师回复： > 是的。栈里面存放的是元素的下标。不是元素本身 ##### **北： > 希望可以有JS解法让前端方向也能碾压算法 ###### 编辑回复： > 可以考虑哦 ##### **生： > 例3 总感觉是o（n^2） ###### 讲师回复： > 首先我们看空间复杂度：这个就是看你的栈申请了多少空间。比如最差的时候，有多少个元素在栈里面。那么这个就是你的空间复杂度。关于时间复杂度，对于栈和队列我有一个比较巧妙的办法就是：只看单个元素的入栈次数，出栈栈次数。如果每个元素都是只是入栈一次，出栈一次，那实际上就是相当于每个元素访问了一遍。所以就是O(N) 你可能会想，啊，一个元素入栈的时候，不是还会把很多元素弹栈么？但是这个只是把入栈的顺序打乱了。比如当单调栈，A要入栈时，要把BC两个元素弹栈。以前是A进,B进,C进,C弹,B弹,A弹。=> 现在变成了B进C进C弹B弹A进A弹。只是换了一种排列组合而已，时间复杂度并没有变。 ##### pmk： > 老师您好，关于大鱼吃小鱼C++代码判断条件这里，while (!t.empty() D == L)，栈 t一开始不就是空的吗？这个while还能继续下去吗 ###### 讲师回复： > 第一轮的话while循环确实是不会进去的。但是不会进去的话，has_eat就是false。如果为false，就需要执行t.push(i); 然后在第二轮里面栈就非空了，就需要做出判断了 ##### **烽： > 面积题我的思路是：1、保底面积 = 最短的木板*木板总数；2、用递减栈放木板，每次入栈我都更新一次最长板面积 = Math.max(最长板面积，temp),temp = 栈顶 * 栈宽；3、返回Math.max(保底面积，最长板面积)。 ###### 讲师回复： > 赞。可以看一下参考答案：https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/01.Stack/84.柱状图中最大的矩形.2.java https://github.com/lagoueduCol/Algorithm-Dryad/blob/main/01.Stack/84.柱状图中最大的矩形.java ##### **鹏： > 老师您好，大鱼吃小鱼那道题：A[4] 发现有左边 A[3]，A[3] 就匹配成功。这句话没看懂啥意思。题目说都和右面的匹配，跟左面有啥关系呢？ ###### 讲师回复： > 根据你的提问，我觉得你应该问的是例3.也就是找右边最小的数。在这里，我需要稍做提醒。你需要采用一点逆向的思路。我们是在找每个元素右边离我最近且最小的元素。但是你也可以反过来想，我也可以认为是在用右边的更小的数x，来找x的左边，并且比x大的数。 ##### **盼： > 老师讲的很好，希望能出个javascript版本🙏🙏🙏 ###### 编辑回复： > 感谢小伙伴的认可，后续会根据大家的需求补充其他语言的代码，比心～ ##### **宇： > 感觉找左边第一个比自己小的这个题目描述可以再完善一下，应该是找左边离自己最近小的数的位置，因为不知道找的第一个是最左边算第一个，还是离得最近算第一个。然后看了一下解析是找左边最近的 ###### 讲师回复： > 赞。已经更新为: 数组中元素左边离我最近且比我小的元素的位置数组中元素左边离我最近且比我大的元素的位置 ##### *涛： > 老师鱼那题是缺少个条件沿着某个方向顺序排序 ###### 讲师回复： > 不需要沿着某个方向“顺序排序（没太看懂顺序排序的意思，暂且理解为向左边游的归一组排序，向右边游的放一组排序）”。比如例子：用>表示向右游，<表示向右游。输入：3> 5> <4.那么游动时，5>会吃掉<4, 然后剩下3>, 5>。而输入：5>, 3> <4，那么游动时，3>, <4相遇，<4吃掉3>，然后5>, <4再相遇。5>吃掉<4，最后剩下5>。 ##### **健： > 老师，你好，字典序最小的 k 个数的子序列中C++版本的代码有个小问题，在初始化ans的时候，大小应该是k ###### 讲师回复： > 谢谢指正，代码已更新！ ##### **用户0827： > 求js版本 ##### Q： > 老师，你好，能否最后提供一批在leetcode上类似的问题，那边便于学习和巩固 ###### 讲师回复： > 我以前在学习和练习的时候，采用的是将tag设置为Stack或者栈。然后再按照难度从易到难排个序，就一个一个开始写了。当然这里有很多问题是可以不用栈的。但是既然我都选了练习栈，那我在练习的时候，就一定要用栈来做实现。题的话，基本上就分为两类，普通栈。单调栈。 ##### **方： > 长路漫漫太南了每个人接受程度不一样我对算法领悟不是很高😭 但是我会多看几遍哪里不懂就翻过去再看几遍在纸上画画动手敲代码知识不会凭白无故进入大脑 ###### 编辑回复： > 小伙伴加油哦！！！ ##### **佳： > 例4的思考题能出个动画或者图解啥的嘛，没太找到规律啊 ###### 讲师回复： > 一个模块的思考题。会在专门一个模块的加餐中（也就是数据结构的一题多解后面会专门有一讲，讲这个模块中的练习题）详细讲解。到时候会详细画个动图，手把手教你的。^_^。目前代码只是直接给出了答案。到时候会把解法二的两个性质详细介绍。 ##### *旭： > 例题1还要考虑一下特殊字符（中文的“（”）和字符内容（“aa”），当然这个有点过于牵强了，这个问题属于“边界”情况，可以用个正则表达式进行过滤。 ###### 讲师回复： > 鉴于这个是面试专栏。在面试中的做法是，先和面试官沟通好有没有这种需求。把这种要求呢，放到需求层面来处理。减轻你面试的时候要写的代码的工作量和问题的边界。然后再看工程中的做法。工程中应该是强调一个函数做一个事儿。那么检查输入是否有非法字符，可能需要在另外一个函数来完成。比如boolean hasUnsupportedCharacter(String s) ##### *超： > 有js版本吗😂 ##### **3302： > 老师，请问例题三中，不用考虑边界情况吗？比如数组长度为1和为0的时候。若数组长度为0，是直接返回空吗？ ###### 讲师回复： > 在真实的面试中是需要考虑的。特别是微软的面试。如果是这种未定义的情况。或者说，面试题目中没有明确说明的情况。比如为空的时候返回什么？在真实的面试中需要和面试官商定。或者说你向他建议返回null还是new int[0] ##### **平： > // 如果递增栈里面的数太多，那么我们只需要取出前k个就可以了。 // 多余的栈中的元素需要扔掉。 “>while (s.size() k) { }这行代码是不是多余了，上面while中(s.size() + left k)不已经确定了stack栈中数据不会大于k吗 ###### 讲师回复： > // 注意我们想要提取出k个数，所以注意控制扔掉的数的个数 while (!s.empty() && (s.size() + left > k) && s.peek() > x) 这个while循环并不能保证栈中的个数。因为这里是三个条件都要满足。你可以试一下数组。[1, 2, 3, 4 ,5 , 6, 7, 8] k = 3 最终是会把所有的元素都入栈的。 ##### **6011： > 妙啊喵啊 ##### **用户0441： > 动图怎么做，能详细一点吗？draw.io做图，PPT做动画？怎么结合在一起？ ###### 编辑回复： > 和小伙伴说的一样，用draw.io做图，PPT做动画，具体的操作过程一两句描述不清，小伙伴可以去网上查查哈 ##### **鹏： > 老师您好，例4题不明白最小数是啥意思，[2,6]为啥是最小呢？2最小，为啥[2,6]是最小呢?比如题意是连续k个数的平均数最小，就是不理解最小说是依据啥 ###### 讲师回复： > 原来文章中的表述并不清晰，现在用更加严谨一点的语言来描述。已经优化了例4的题目描述，可以重新再看看，有问题我们随时交流 ##### **2703： > int n = heights.length;//left[i]是 i 左侧且最近的小于height[i]的柱子索引int[] left = new int[n];//right[i]是 i 右侧且最近的小于height[i]的柱子索引int[] right = new int[n];//递增栈Stack”>new Stack”>;for (int i = 0; i “>; i++) { while (!st1.isEmpty() heights[st1.peek()]) { right[st1.peek()] = i; st1.pop(); } left[i] = st1.isEmpty() ? -1 : st1.peek(); st1.push(i);}while (!st1.isEmpty()) { right[st1.pop()] = n;}int ans = 0;for (int i = 0; i “>; i++) { ans = Math.max(ans, (right[i] - left[i] - 1) * heights[i]);}return ans; ##### *斌： > up

文章目录