Leetcode—栈相关

　　这篇文章是LeetCode上栈相关的题目，只涉及思路和方法，没有完整代码。

　　20、给定一个只包括 ‘('，')'，'{'，'}'，'['，']’ 的字符串，判断字符串是否有效

// 左括号必须用相同类型的右括号闭合。 
// 左括号必须以正确的顺序闭合。 
// 注意空字符串可被认为是有效字符串。 
//
// 示例 1:
// 输入: "()"
//输出: true
//
// 示例 2: 
// 输入: "()[]{}"
//输出: true
//
// 示例 3: 
// 输入: "(]"
//输出: false
//
// 示例 4: 
// 输入: "([)]"
//输出: false
// 
// 示例 5: 
// 输入: "{[]}"
//输出: true

　　这个题目也算是经典的使用栈的题目了，题目本身的约束条件是很多的，题目本身没有太多说的，使用一个栈来存储遍历的每一个字符，如果遇到左括号，就入栈；如果遇到右括号，则出栈，判断其是否匹配，最后判断一下栈是否为空即可。

　　42、给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

　　这个题目需要看着官网的图，才比较容易理解，对照着图去梳理题意，至少可以找到比较暴力的解法的……比如可以遍历整个数组，计算每一列可以装的水的份数，那么每一列可以装的水的份数取决于什么呢？仔细想一下你用两个隔板来装水，那么能装的水是取决于更矮的那个隔板的高度的，也就是每一列可以装的水的份数是取决于当前列左侧和右侧各自最高的隔板的高度，注意这里你仔细思考就会发现这是嵌套的for循环，因此是O(n^2)的时间复杂度。思路就是这样，代码实现也比较简洁。

　　动态规划：前面我们已经看到了，在循环内部，我们每次找当前列左侧的最高高度和右侧的最高高度时，都又去遍历了一次整个数组（或者说半个数组），这其实是非常不合适的，所以还是可以继续优化一下。我们用两个数组maxLeft[i]记录第i列左边最高的墙高度（不包括自身），用 maxRight[i]来记录第i列右侧最高的墙高度（不包括自身），先提前记录下来，这样后续直接去这个数组里查就可以了。

　　如何通过遍历计算出每一列左侧和右侧各自的最高高度呢？这里就是动态规划的思想了，这里注意，对于第0列和最后一列，是不需要计算出它左侧（右侧）的最高高度的，可以简单记为0，那么maxLeft[i]其实就是Math.max(maxLeft[i - 1], height[i - 1])，这一步应该可以理解，只需要这样一直递推下去，就可以求出maxLeft了，同理也可以计算出maxRight（只不过从后往前）。这样通过提前计算，我们就将上面那个解法的时间复杂度降到了O(n)。耗时显著减少。

　　优化版本的动态规划：仔细思考前面的思路，我们就会发现，maxLeft和maxRight这两个数组中的每一个元素，我们都只使用了一次，所以可以考虑一下，不使用一个数组，而只使用一个变量来解决，事实上，这里的maxLeft是可以不用的（但是maxRight是需要的），转而在遍历数组的时候，每次遍历到当前元素的时候，实时计算当前元素的左侧中最大的元素，这样也是可以的。需要注意的是，这一步的优化，只能去掉 maxLeft数组，不能去掉maxRight数组，因为right数组是从后往前遍历计算得到的。除非你最终的遍历也是从后往前计算，这样也可以，但是始终需要保留一个数组。

　　双指针：这是这道题的tag之一（还有栈），

　　栈：栈和双指针都不那么容易理解，这个题真是有点意思了，反倒是动态规划的思路比较清晰直接，先存疑吧。

　　84、给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为1

　　这道题目也算是经典题目之一了，可以用一些暴力方法求解，也可以用栈，甚至可以用一些快排的思想来做。暴力的思想就是，只需要求出每一种高度的柱子对应的最大面积即可，如果求高度为 3 的面积最大的，我们只需要遍历每一个高度，然后看连续的大于等于 3 的柱形有几个，如果是n个，那么此时的面积就是 3 * n。所以高度确定的话，我们只需要找连续的大于等于 3 的柱形个数，也就是高度。

　　155、设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈

// push(x) —— 将元素 x 推入栈中。 
// pop() —— 删除栈顶的元素。 
// top() —— 获取栈顶元素。 
// getMin() —— 检索栈中的最小元素。

　　其实细看这道题目，只限制了可以在常数时间内查到栈中的最小元素，其他并未做要求，可以实现的方法也非常多，下面研究一下每一种方法：

1）使用两个原生栈来实现，一个普通栈来提供正常的方法，一个最小栈来保存当前栈中的最小元素。元素入栈：普通栈正常push，最小元素栈如果为空或者最小元素栈的栈顶元素大于当前入栈元素，则最小栈也push；元素出栈：普通栈正常pop，如果pop的元素和最小栈的栈顶元素相等，那么最小栈也pop，否则不处理；获取最小元素则直接返回最小栈的栈顶元素即可。
2）第一种方法用了另一个栈来保存最小值，实际上，我们可以只用一个变量来记录最小值，但是在入栈的时候会有一些变化，如果入栈的元素比当先min值更小，那么就先把当前最小值入栈，然后更新min，这里也就是连续入栈了两个元素；那么在对应出栈的时候，需要判断出栈的元素是否等于当前min值，如果相等，那还需要再次出栈一个元素，并且把min赋值给这个元素。

　　后面还有两种比较奇妙的方法，甚至最后一种方法并不使用栈本身来实现，而是使用一个链表（因为题目并没有要求其他操作的时间复杂度），只不过这个链表节点需要增加一个元素，来保存每加入一个节点后的min值。这两种方法都值得思考一番。

　　225、使用队列实现栈的下列操作

// push(x) -- 元素 x 入栈 
// pop() -- 移除栈顶元素 
// top() -- 获取栈顶元素 
// empty() -- 返回栈是否为空 
// 
// 你只能使用队列的基本操作-- 也就是 push to back, peek/pop from front, size, 和 is empty 这些操作是合法的。

　　用队列来实现栈，和用栈实现队列，本质上都是在考察栈和队列的不同点。思考一下就发现，我们将一个元素offer到队列的时候，要出队也是最小入队的被移出，但是栈是反过来的，所以你用队列来实现栈的时候，简单一点可以这样：入栈的时候，队列正常offer一个元素；出栈的时候，你需要出的是队列的最后进来的那个元素，所以应该先把前面的出队（可以保存到一个临时的队列中），直到只剩一个元素了，这个元素就是要出栈的那个元素，然后将临时队列的元素再依次入队列；判断栈是否为空即复用队列的判空方法；获取栈顶元素和出栈一样，但是最后剩下的那个元素还需要再次入队。

　　上面这种方法我们其实是在push入栈时直接使用offer，修改出栈的pop方法，也可以换一种思路，在入栈时，每次push一个元素，我们就把之前已经在队列中的元素出队并再次入队，这样就实现了队列的首元素永远是刚刚加入进来的元素，这样也就实现了一个栈的思想，而且更加简洁。

　　232、使用栈实现一个队列

　　这个题目和前面的题本质上属于一个类型，具体来说，也有两种思路，要么在push的时候就做文章（这时候也需要一个临时栈先保存当前栈的元素），要么在pop的时候使用一个临时栈去保存先弹出的那几个元素。题目本身还是比较简单的。