首页 ›存档› 技术 › 查看内容

算法面试精要准备 - 栈

2018-3-30 13:00 |来自: 互联网 305 0

摘要: 栈是什么呢？很简单，就是实现后进先出(LIFO)的数据结构，在某些算法题中，就会利用栈的这种特性来达成目的。所有代码都已经同步至 https://github.com/woaitqs/common_algorithm，欢迎关注。 0X000 例子1 我们从最 ...

栈是什么呢？很简单，就是实现后进先出(LIFO)的数据结构，在某些算法题中，就会利用栈的这种特性来达成目的。所有代码都已经同步至 https://github.com/woaitqs/common_algorithm，欢迎关注。

0X000 例子1

我们从最直接的例子上入手，看看栈是如何帮助我们的。

原题来源：leetcode-20

Given a string containing just the characters ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ and ‘]’, determine if the input string is valid.The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

题目大意是，给出一个包含 ‘(‘, ‘)’, ‘{‘, ‘}’, ‘[‘ 和 ‘]’ 的字符串，判断这个字符串是否符合数学常识，也就是是否成双成对。

利用栈的特性，将属于带有左性质(左小括号，左大括号等等)的符号入栈，当遇到右性质的符号就出栈，同时比较两个符号是否成对。

0X001 例子2

原题来源：leetcode-94

二叉树的中序遍历题目，一般有递归方式与非递归方式两种。这里不介绍递归方式，而是用栈的特性，来帮助我们完成遍历。

维护一个栈 stackNodes 和一个当前节点 traversalNode。初始时将 traversalNode 赋值为根节点。
将当前节点 traversalNode 的左子链上的节点逐个推入栈中，直到没有左儿子。
取出栈顶的节点，访问该节点，将 traversalNode 赋值为该节点的右儿子。
不断执行 2，3，直到栈为空且当前节点也为空。

0X002 例子3

最后再来看看一个复杂的例子。

原题来源：leetcode-84

Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.

给定一个非负整数的数组，这个数组如上图一样，可以用直方图的形式来展示，求能够组成的最大矩形的面积。在上图中，红色矩形的那一块就是最大的面积。

这个题目也是对栈的利用。我们先想想一个递增的序列，在这种情况下，矩形最大的面积一定是可以连续计算的，但一定遇到下跌的数字，出现了断层，这一块区域就不能连续计算了。由此我们通过栈的方式，来维持一个递增序列，当遇到下降时就进行计算一次。这里的逻辑相对复杂，大家需要多花一些时间来理解。