脑图：http://naotu.baidu.com/file/3bc98871b57aa37136f7db9c7c603376?token=7a4113ffec3d8fba
20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
- 栈
遍历数组，左括号入栈；右括号判断与栈顶元素是否匹配，匹配出栈；否则return false；
遍历完成之后，判断栈是否为空，空则 return true；否则 return false；
图解
题解：https://www.jianshu.com/p/058f90ed4ae9
155. 最小栈
设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
- 栈
利用辅助栈保存最小值
辅助栈的数据与数据栈是同步的
入栈时，判断入栈的数据与辅助栈的栈顶数据哪个小，取小值入辅助栈
出栈时，数据栈和辅助栈同时出栈
图解
- 链表
利用链表
链表中保存
当前值
最小值
上一个节点
入栈时，入栈的值与链表中当前节点的最小值比较，最小值保存到下一个节点的最小值中
图解
题解：https://www.jianshu.com/p/620194367c3f
641. 设计循环双端队列
设计实现双端队列。
你的实现需要支持以下操作：
MyCircularDeque(k)：构造函数,双端队列的大小为k。
insertFront()：将一个元素添加到双端队列头部。 如果操作成功返回 true。
insertLast()：将一个元素添加到双端队列尾部。如果操作成功返回 true。
deleteFront()：从双端队列头部删除一个元素。 如果操作成功返回 true。
deleteLast()：从双端队列尾部删除一个元素。如果操作成功返回 true。
getFront()：从双端队列头部获得一个元素。如果双端队列为空，返回 -1。
getRear()：获得双端队列的最后一个元素。 如果双端队列为空，返回 -1。
isEmpty()：检查双端队列是否为空。
isFull()：检查双端队列是否满了。
循环双端队列
队列成一个圆环形状
设定开始位置
尾插数据，rear指针向后移动 ++
尾删数据，rear指针向前移动 --
头插数据，prior指针向前移动 --
头删数据，prior指针向后移动 ++
设计循环双端队列空间比总数大一，避免空和满无法判断
判空
rear == prior
判满
(rear+1)%capacity == prior
插入数据先判满
删除数据先判空
图解
题解：https://www.jianshu.com/p/02218a7eb8ae
42. 接雨水
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。
-
暴力解法
两次循环
接雨水的量 = min(maxLeft, maxRight) - height[i]
外层循环遍历数组
当前位置为基准点，向左右遍历，找到左右的最大值，取两个最大值的最小值 - 当前高度 即为当前位置可接雨水量
图解
-
动态规划
空间换时间
先遍历得到左边最大值数组和右边最大值数组
然后遍历数组进行计算接雨水量
min(maxLeft, maxRight) - currentHeight -
双指针
头尾指针
头尾索引位置没有两边的边界，所以无法接雨水，作为左右最大值的初始化值
left初始化值为1，right初始化值为count-2
头尾指针向中间靠拢
判断 maxLeft > maxRight
计算左边
判断 leftHeight >= maxLeft
更新maxLeft
否则，计算当前索引接雨水量 maxLeft - leftHeight
最后
left++
右边同上
图解
-
栈
单调栈
单调递减栈
栈中保存索引
当前索引的值小于栈顶元素的值，入栈
反之，计算接雨水量
题解：https://www.jianshu.com/p/4f148c40cb69
84. 柱状图中最大的矩形
给定 n 个非负整数，用来表示柱状图中各个柱子的高度。每个柱子彼此相邻，且宽度为 1 。
求在该柱状图中，能够勾勒出来的矩形的最大面积。
以上是柱状图的示例，其中每个柱子的宽度为 1，给定的高度为 [2,1,5,6,2,3]。
图中阴影部分为所能勾勒出的最大矩形面积，其面积为 10 个单位。
- 暴力法
面积 = (right - left) * minHeight(right和left之间)
计算出所有的柱形之间的面积，取最大值 - 栈
栈
单调栈
单调递增栈
遍历数组元素，>= 栈顶元素，入栈 < 栈顶元素(右边界)， 出栈，直到栈顶元素的值 <= 当前值(得到左边界)
面积 =（right - left + 1） * height[currentIndex]
最后得到最大面积
图解
网友评论