题目描述

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。 实现 MinStack 类: MinStack() 初始化 void push(int val) 将元素推入堆栈 void pop() 删除堆栈顶部的元素 int pop() 获取堆栈顶部的元素 int getMin() 获取堆栈中的最小元素

题解：

这道题首先要满足堆栈的特性 LIFO，其次是能够在常数时间内获取当前栈中最小的元素，因此我们可以用堆栈保存 个二元组，二元组的第一个元素是存入栈中的值，第二个元素是当前元素作为栈顶元素的时候，栈中的最小值。有 了这个思路，代码实现起来就很简单了。

class MinStack {...

题目描述

给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。 求在该柱状图中，能够勾勒出来的矩形的最大面积。

解法一：暴力求解

主要思路是，遍历每个柱子，然后往柱子左右两边寻找比当前柱子矮的位置，从而计算出，以当前柱子为高度，所能围成的最大面积。 然后将这些面积中最大的值返回即可。暴力求解的时间复杂度为O(n^2)

不过我尝试过各种暴力求解，在 leetcode 中提交后都会超时。

class Solution {
public:
    int largestRectangleInHistogram(const std::vector<int>& inputs) {...

题目描述

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。 有效字符串需满足： 左括号必须用相同类型的右括号闭合。 左括号必须以正确的顺序闭合。 每个右括号都有一个对应的相同类型的左括号。

解法一：stack

这道题目是典型的堆栈数据结构的应用，虽然思路很清晰，代码也很简单，但是要注意逻辑的严谨性。尤其是在判断 栈顶元素是否匹配之前，要先判断栈是否为空。

class Solution {
public:
    bool...

题目描述

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（push、pop、peek、empty）： 实现 MyQueue 类：

• void push(int x) 将元素 x 推到队列的末尾
• int pop() 从队列的开头移除并返回元素
• int peek() 返回队列开头的元素
• boolean empty() 如果队列为空，返回 true ；否则，返回 false

说明： 你 只能 使用标准的栈操作 —— 也就是只有 push to top, peek/pop from top, size, 和 is empty 操作是合法的。 你所使用的语言也许不支持栈。你可以使用 list 或者 deque（双端...