01 | 栈:从简单栈到单调栈,解决经典栈问题

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

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

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

栈的特性与使用

单调栈的解题技巧

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

栈的特性与使用

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

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

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

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

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

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

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

输入:"()"

输出:true

解释:(),()(),(())是合法的。)(,()(,(()是非法的。

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

复制代码boolean isValid(String s);

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

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

模拟:模拟题目的运行。

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

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

边界:考虑特殊情况。

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

1. 模拟

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

2. 规律

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

(1)每个左括号'('或者右括号')'都完成配对,才是合法的。

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

(3)奇数长度的字符串总是非法的。

3. 匹配

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

4. 边界

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

字符串为空

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

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

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

当遇到左括号'('时,进行压栈操作

当遇到右括号')'时,进行弹栈操作

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

【代码】到这里时,你可以写出以下核心代码(解析在注释里):

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

代码:Java,C++,Python

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

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

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

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

1. 深度扩展

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

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

实际上,就是把入栈与出栈变成了 leftBraceNumber 的加减。代码如下(解析在注释里):

复制代码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

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

复制代码int solution(int[] Size, int[] Dir);

题目的示意图如下所示:

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

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

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

1. 模拟

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

复制代码Size = [4, 3, 2, 1 5], Dir = [0, 1, 0, 0, 0]

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

2. 规律

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

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

其他情况没有鱼被吃掉。

3. 匹配

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

4. 边界

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

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

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

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

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

【代码】根据之前的思考,可以得到如下解法(解析在注释里):

复制代码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 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。

复制代码接口: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.

【代码】到此为止,相信你已经可以根据思路写出代码了,代码如下(解析在注释里):

复制代码public static int[] findRightSmall(int[] A) {  // 结果数组  int[] ans = new int[A.length];  // 注意,栈中的元素记录的是下标  Stack 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。

复制代码接口:int[] findSmallSeq(int[] A, int k);

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

1. 模拟

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

2. 规律

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

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

3. 匹配

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

4. 边界

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

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

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

复制代码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 个了。所以不能再利用单调性来弹出栈中元素了。

【代码】到这里,相信你已经可以根据思路写出代码了,代码如下(解析在注释里):

复制代码public int[] findSmallSeq(int[] nums, int k) {  int[] ans = new int[k];  Stack 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 队列与单调队列的深挖与扩展,记得按时来探险。

(0)

相关推荐