队列、栈、堆

1. 队列、栈、堆简介

队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。

栈（stack）又名堆栈，它是一种运算受限的线性表。限定仅在表尾进行插入和删除操作的线性表。这一端被称为栈顶，相对地，把另一端称为栈底。向一个栈插入新元素又称作进栈、入栈或压栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素；从一个栈删除元素又称作出栈或退栈，它是把栈顶元素删除掉，使其相邻的元素成为新的栈顶元素。

注意：队列与栈的添加与操作操作皆为o(1),查找是o(n)。

我们完全可以把堆（以下全都默认为最大堆）看成一棵完全二叉树，但是位于堆顶的元素总是整棵树的最大值，每个子节点的值都比父节点小，由于堆要时刻保持这样的规则特性，所以一旦堆里面的数据发生变化，我们必须对堆重新进行一次构建。

2. 如何实现队列、栈、堆

队列与栈可以由多种基本数据结构实现。很多语言内置语法已实现常用队列与栈。
为了方便使用，笔者使用go语言数组实现了各种栈与队列。（go语言还未有队列与栈的内置实现）

注意：笔者实现的队列与栈未处理下标异常情况，仅供练习与刷题使用，勿用于生产环境。

基本队列：

type MyQueue struct {
    queue []int
}
//初始化队列
func NewQueue() MyQueue{
    return MyQueue{}
}
//返回队列长度
func (m *MyQueue) Len()int{
    return len(m.queue)
}
//查看队列头元素
func (m *MyQueue) Peek()int{
    return m.queue[0]
}
//元素出队列
func (m *MyQueue) Poll()int{
    top := m.Peek()
    m.queue = m.queue[1:]
    return top
}
//元素进队列
func (m *MyQueue) Add(x int){
    m.queue = append(m.queue,x)
}

双端队列：

type MyDeque struct {
    deque []int
}
//初始化双端队列
func NewDeque() MyDeque{
    return MyDeque{}
}
//返回双端队列长度
func (m *MyDeque) Len()int{
    return len(m.deque)
}
//将元素插入到队列头部
func (m *MyDeque) InsertFront(x int){
    m.deque = append([]int{x},m.deque...)
}
//将元素追加到队列尾部
func (m *MyDeque) InsertLast(x int){
    m.deque = append(m.deque,x)
}
//从头部删除元素
func (m *MyDeque) DeleteFront()int{
    num := m.deque[0]
    m.deque = m.deque[1:]
    return num
}
//从尾部删除元素
func (m *MyDeque) DeleteLast()int{
    num := m.deque[m.Len()-1]
    m.deque = m.deque[:m.Len()-1]
    return num
}
//获取头部元素
func (m *MyDeque) GetFront()int{
    return m.deque[0]
}
//获取尾部元素
func (m *MyDeque) GetRear()int{
    return m.deque[len(m.deque)-1]
}

单调队列：

type MyQueue struct {
    queue []int
}
//初始化队列
func NewQueue() MyQueue{
    return MyQueue{}
}
//返回队列长度
func (m *MyQueue) Len()int{
    return len(m.queue)
}
//查看队列头元素
func (m *MyQueue) Peek()int{
    return m.queue[0]
}
//元素出队列
func (m *MyQueue) Poll()int{
    top := m.Peek()
    m.queue = m.queue[1:]
    return top
}
//元素进队列
func (m *MyQueue) Add(x int){
    //若队尾元素大于待添加元素，则移除队尾元素,保证队列是单调递增的
    for m.Len() > 0 && m.queue[m.Len()-1] > x{
        m.queue = m.queue[:m.Len()-1]
    }
    m.queue = append(m.queue,x)
}

基本栈：

type MyStack struct {
    stack []int
}
//初始化栈
func NewStack() MyStack{
    return MyStack{}
}
//返回栈长度
func (m *MyStack) Len()int{
    return len(m.stack)
}
//查看栈顶元素
func (m *MyStack) Top()int{
    return m.stack[len(m.stack)-1]
}
//弹出栈顶元素
func (m *MyStack) Pop()int{
    pop := m.Top()
    m.stack = m.stack[:len(m.stack)-1]
    return pop
}
//往栈中压入新元素
func (m *MyStack) Push(x int){
    m.stack = append(m.stack,x)
}

大根堆（用数组方式实现）：

type Heap struct{
    heap []int
}
func Init(nums []int)*Heap{
    h := &Heap{
        heap : nums,
    }
    h.init()
    return h
}
func (h *Heap)init(){
    //初始化时不断的下沉
    n := h.len()
    for i := n/2-1;i >= 0;i--{
        h.down(i)
    }
}
//返回堆的长度
func(h *Heap)len()int{
    return len(h.heap)
}
//交换元素
func(h *Heap)swap(i,j int){
    h.heap[i],h.heap[j] = h.heap[j],h.heap[i]
}
//比较大小
func(h *Heap)more(i,j int)bool{
    return h.heap[i] > h.heap[j]
}
//上升
func (h *Heap)up(i int){
    for {
        p := (i-1) / 2 //父节点
        if p == i || h.more(p,i){
            break
        }
        h.swap(p,i)
        i = p
    }
}
//添加元素时，会首先把元素添加到末尾，然后去和父元素进行比较直到每个树的根元素都大于子树的数。
func (h *Heap)Push(v int){
    h.heap = append(h.heap,v)
    h.up(h.len()-1)
}
//下沉
func (h *Heap)down(i int){
    for {
        left := 2*i+1 //左子节点
        //越界判断
        if left < 0 || left >= h.len(){
            break
        }
        j := left
        //下沉时要去和数值大的子树进行比较。
        if right := left + 1;right < h.len() && h.more(right,left){
            j = right
        }
        if h.more(i,j){
            break
        }
        h.swap(i,j)
        i = j
    }
}
//移除元素
func (h *Heap)Remove(i int)(int,bool){
    if i < 0 || i >= h.len(){
        return 0,false
    }
    //移除元素时,会先将移除元素移动到最末端的位置，然后再重新调整位置。
    last := h.len()-1
    h.swap(last,i)
    x := h.heap[last]
    h.heap = h.heap[0:last]
    if i == 0 || (h.heap[i] < h.heap[(i-1)/2]){
        h.down(i)
    }else{
        h.up(i)
    }
    return x,true
}
func (h *Heap)Pop()(int,bool){
    return h.Remove(0)
}

大根堆（实现contain/heap接口)：

type Interface interface {
    sort.Interface
    Push(x interface{}) // add x as element Len()
    Pop() interface{}   // remove and return element Len() - 1.
}
func (h IntHeap) Len() int { return len(h) }
// Less 为了实现大根堆，Less在大于时返回小于
func (h IntHeap) Less(i, j int) bool { return h[i] > h[j] }
func (h IntHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

3. 队列经典题目必须 掌握

232. 用栈实现队列简单

请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作（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（双端队列）来模拟一个栈，只要是标准的栈操作即可。

进阶：
你能否实现每个操作均摊时间复杂度为 O(1) 的队列？换句话说，执行 n 个操作的总时间复杂度为 O(n) ，即使其中一个操作可能花费较长时间。

示例：
输入：
[“MyQueue”, “push”, “push”, “peek”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 1, 1, false]
解释：
MyQueue myQueue = new MyQueue();
myQueue.push(1); // queue is: [1]
myQueue.push(2); // queue is: [1, 2] (leftmost is front of the queue)
myQueue.peek(); // return 1
myQueue.pop(); // return 1, queue is [2]
myQueue.empty(); // return false

提示：
1 <= x <= 9
最多调用 100 次 push、pop、peek 和 empty
假设所有操作都是有效的 （例如，一个空的队列不会调用 pop 或者 peek 操作）

题解概要：

1.使用两个栈，一个栈进，另一个栈出。
2.当调用pop或peek操作时，将入栈元素弹出并压入到出栈中，再将出栈栈顶返回即可。
动画：
点击查看【bilibili】
代码：

type MyQueue struct {
    inStack []int     //入栈
    outStack []int      //出栈
}
func Constructor() MyQueue {
    return MyQueue{}
}
func (q *MyQueue) Push(x int) {
    q.inStack = append(q.inStack,x)
}
func (q *MyQueue) in2out() {
    for len(q.inStack) > 0 {
        last := len(q.inStack) -1
        q.outStack =  append(q.outStack,q.inStack[last])
        q.inStack = q.inStack[:last]
    }
}
func (q *MyQueue) Pop() int {
    if len(q.outStack) < 1{
        q.in2out()
    }
    num := q.outStack[len(q.outStack)-1]
    q.outStack = q.outStack[:len(q.outStack)-1]
    return num
}
func (q *MyQueue) Peek() int {
    if len(q.outStack) < 1{
        q.in2out()
    }
    return q.outStack[len(q.outStack)-1]
}
func (q *MyQueue) Empty() bool {
    return len(q.inStack) == 0 && len(q.outStack) == 0
}

剑指 Offer 59 - I. 滑动窗口的最大值 困难

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

示例:
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置 最大值
———————- ——-
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

提示：
你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。

题解概要：

使用单调递减队列记录每个滑窗的最大值。
图解：

代码：

type Deque struct{
    Queue  []int  //单调递减队列
}
func Constructor() Deque {
    return Deque{}
}
// 单调递减队列的push方法,保证队列是递减的
func (d *Deque) Push(val int){
    for len(d.Queue) > 0 && d.Queue[len(d.Queue)-1] < val{
        d.Queue = d.Queue[:len(d.Queue)-1]
    }
    d.Queue = append(d.Queue,val)
}
//返回单调队列最大值
func (d *Deque) Max() int{
    if len(d.Queue) <= 0{
        return -1
    }
    return d.Queue[0]
}
// 判断val是否在队列头部
func (d *Deque) Remove(val int) {
    if len(d.Queue) <= 0{
        return 
    }
    if d.Queue[0] == val{
        d.Queue = d.Queue[1:]
    }
}
func maxSlidingWindow(nums []int, k int) []int {
    c := Constructor() //初始化单调队列
    res := []int{}     //存放结果集
    l,r := 0,0         //左指针与右指针
    for r < len(nums){
        c.Push(nums[r]) //入队列
        //出滑窗
        for r-l+1 > k{
            c.Remove(nums[l])
            l +=1 
        }
        //更新结果集
        if r-l+1 == k{
            res = append(res,c.Max())
        }
        r += 1
    }
    return res
}

225. 用队列实现栈 简单

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：

void push(int x) 将元素 x 压入栈顶。
int pop() 移除并返回栈顶元素。
int top() 返回栈顶元素。
boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

你只能使用队列的基本操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

示例：
输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]
解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

题解概要：

1. 需借助辅助队列。每次添加元素时，先将元素添加到辅助队列，再将主队列元素依次加入到辅助队列。最后将辅助队列赋值给主队列，并将辅助队列设置为空队列。
2. 这就保证主队列元素为先入后出。

动画如下：

动画：
点击查看【bilibili】
代码：

type MyStack struct {
    q1 []int   //主队列
    q2 []int   //辅助队列
}
/** Initialize your data structure here. */
func Constructor() MyStack {
    return MyStack{}
}
/** Push element x onto stack. */
func (this *MyStack) Push(x int)  {
    this.q2 = append(this.q2,x)
    this.q2 = append(this.q2,this.q1...)
    this.q1 = this.q2
    this.q2 = []int{}
}
/** Removes the element on top of the stack and returns that element. */
func (this *MyStack) Pop() int {
    pop := this.Top()
    this.q1 = this.q1[1:]
    return pop
}
/** Get the top element. */
func (this *MyStack) Top() int {
    return this.q1[0]
}
/** Returns whether the stack is empty. */
func (this *MyStack) Empty() bool {
    return len(this.q1) == 0
}

剑指 Offer 59 - II. 队列的最大值 中等

请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。

若队列为空，pop_front 和 max_value 需要返回 -1

示例 1：
输入:
[“MaxQueue”,”push_back”,”push_back”,”max_value”,”pop_front”,”max_value”]
[[],[1],[2],[],[],[]]
输出: [null,null,null,2,1,2]

示例 2：
输入:
[“MaxQueue”,”pop_front”,”max_value”]
[[],[],[]]
输出: [null,-1,-1]

限制：
1 <= push_back,pop_front,max_value的总操作数 <= 10000
1 <= value <= 10^5

题解概要：

1.使用两个队列，一个队列维护元素入队顺序，另一个单调递减队列维护队列最大值。
图解：




代码：

type MaxQueue struct {
    queue   []int     //主队列
    deque   []int     //双端队列
}
func Constructor() MaxQueue {
    return MaxQueue{}
}
func (this *MaxQueue) Max_value() int {
    if len(this.deque) < 1{
        return -1
    }
    return this.deque[0]
}
func (this *MaxQueue) Push_back(value int)  {
    this.queue = append(this.queue,value)
    for len(this.deque) > 0 && this.deque[len(this.deque)-1] < value{
        this.deque = this.deque[:len(this.deque)-1]
    }//保证队列的单调性
    this.deque = append(this.deque,value)
}
func (this *MaxQueue) Pop_front() int {
    if len(this.queue) < 1{
        return -1
    }
    val := this.queue[0]
    this.queue = this.queue[1:]
    if val == this.deque[0] {
        this.deque = this.deque[1:]
    }
    return val
}

862. 和至少为 K 的最短子数组 困难

给你一个整数数组 nums 和一个整数 k ，找出 nums 中和至少为 k 的 最短非空子数组 ，并返回该子数组的长度。如果不存在这样的 子数组 ，返回 -1 。

子数组 是数组中 连续 的一部分。

示例 1：
输入：nums = [1], k = 1
输出：1

示例 2：
输入：nums = [1,2], k = 4
输出：-1

示例 3：
输入：nums = [2,-1,2], k = 3
输出：3

提示：
1 <= nums.length <= 105
-105 <= nums[i] <= 105
1 <= k <= 109

题解概要：

1.使用前缀和与单调队列。
图解：
待补充图解。

代码：

func shortestSubarray(nums []int, k int) int {
    sum := make([]int,len(nums)+1)   //前缀和
    queue := []int{0}                //单调队列
    for i,v := range nums{
        sum[i+1] = sum[i] + v
    }
    res := math.MaxInt32
    for i := 1; i < len(sum);i++ {
        //因为k是正数，如果sum[i-1] >= sum[i]了，就一定不符合条件。所以，要从数组中移除。也就是说，队列是单调自增队列。
        for len(queue) > 0 && sum[queue[len(queue)-1]] >= sum[i]{
            queue = queue[:len(queue)-1]
        }
        queue = append(queue,i)
        //需满足条件sum[i] -queue[0] >= k,但是queue[0]此时有可能为空,应转换不等式。所以sum[i] -k 应该大于等于 queue[0]
        diff := sum[i] - k
        for len(queue) > 0 && diff >= sum[queue[0]]{
            res = min(res,i-queue[0])
            queue = queue[1:]
        } 
    }
    if res == math.MaxInt32 {
        return -1
    }
    return res
}
func min(num1 int,num2 int)int{
    if num2 < num1 {
        return num2
    }
    return num1
}

1438. 绝对差不超过限制的最长连续子数组 中等

给你一个整数数组 nums ，和一个表示限制的整数 limit，请你返回最长连续子数组的长度，该子数组中的任意两个元素之间的绝对差必须小于或者等于 limit 。

如果不存在满足条件的子数组，则返回 0 。

示例 1：
输入：nums = [8,2,4,7], limit = 4
输出：2
解释：所有子数组如下：
[8] 最大绝对差 |8-8| = 0 <= 4.
[8,2] 最大绝对差 |8-2| = 6 > 4.
[8,2,4] 最大绝对差 |8-2| = 6 > 4.
[8,2,4,7] 最大绝对差 |8-2| = 6 > 4.
[2] 最大绝对差 |2-2| = 0 <= 4.
[2,4] 最大绝对差 |2-4| = 2 <= 4.
[2,4,7] 最大绝对差 |2-7| = 5 > 4.
[4] 最大绝对差 |4-4| = 0 <= 4.
[4,7] 最大绝对差 |4-7| = 3 <= 4.
[7] 最大绝对差 |7-7| = 0 <= 4.
因此，满足题意的最长子数组的长度为 2 。

示例 2：
输入：nums = [10,1,2,4,7,2], limit = 5
输出：4
解释：满足题意的最长子数组是 [2,4,7,2]，其最大绝对差 |2-7| = 5 <= 5 。

示例 3：
输入：nums = [4,2,2,2,4,4,2,2], limit = 0
输出：3

提示：
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^9
0 <= limit <= 10^9

题解概要：

1.使用两个队列，一个单调递增队列，一个单调递减队列。
2.再使用滑动窗口模板更新子数组长度的最大值即可。

注意：这道题最简单的方法是使用有序的数据结构，这样就可以在o(1)时间内获得最大值与最小值，从而算出最大绝 对差。

引入大佬题解：https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/solution/he-gua-de-shu-ju-jie-gou-hua-dong-chuang-v46j/

代码：

type  Queue struct{
    minQueue []int  //单调递减队列
    maxQueue []int  //单调递增队列
}
func New() Queue{
    return Queue{}
}
func (q *Queue) pushBack(val int){
    for len(q.maxQueue) > 0 && q.maxQueue[len(q.maxQueue)-1] < val{
        q.maxQueue = q.maxQueue[:len(q.maxQueue)-1]
    }//单调递增队列入队列
    for len(q.minQueue) > 0 && q.minQueue[len(q.minQueue)-1] > val{
        q.minQueue = q.minQueue[:len(q.minQueue)-1]
    }//单调递减队列入队列
    q.maxQueue = append(q.maxQueue,val)
    q.minQueue = append(q.minQueue,val)
}
func (q *Queue) update(val int){
    //滑窗收缩时，更新两个队列的数据。
    if q.maxQueue[0] == val{
        q.maxQueue = q.maxQueue[1:]
    }
    if q.minQueue[0] == val{
        q.minQueue = q.minQueue[1:]
    }
}
//获取绝对差
func (q *Queue) getNum()int{
    return abs(q.maxQueue[0]-q.minQueue[0])
}
//封装绝对值方法
func abs(val int)int{
    if val < 0{
    return -val
    }
    return val
}
//封装两数比较大小方法
func max(num1 int,num2 int)int{
    if num1 > num2{
    return num1
    }
    return num2
}
func longestSubarray(nums []int, limit int) int {
    l,r := 0,0
    res := 0
    q := New()
    for r < len(nums){
           q.pushBack(nums[r])
    //不满足条件时，收缩窗口。
    for q.getNum() > limit{
        q.update(nums[l])
        l += 1
    }
        res = max(res,r-l+1)
        r += 1
    }
    return res
}

总结

1.题目中考察队列较少，多为单调递增或递减队列。
2.求xxx的最大值或xxx的最小值，可以尝试使用队列，这样就能保证整个算法在o(n)时间内，只是牺牲入队列的一些性能。

4. 栈-括号题目必须 掌握

20. 有效的括号简单

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

有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：
输入：s = “()”
输出：true

示例 2：
输入：s = “()[]{}”
输出：true

示例 3：
输入：s = “(]”
输出：false

示例 4：
输入：s = “([)]”
输出：false

示例 5：
输入：s = “{[]}”
输出：true

提示：
1 <= s.length <= 104
s 仅由括号 ‘()[]{}’ 组成

题解概要：

1.创一个存放字符的栈。
2.遇到(、[、{则将对应的括号入栈。(方便后面计算)
3.遇到)、]、}时，判断是否与栈顶元素匹配。若匹配则将栈顶移除,不匹配return false。
4.最后判断栈是否为空,若为空说明是有效的。
图解：

代码：

func isValid(s string) bool {
    stack := []byte{}
    for i,_ := range s{
        if s[i] == '('{
            stack = append(stack,')')
        }else if s[i] == '{'{
            stack = append(stack,'}')
        }else if s[i] == '['{
            stack = append(stack,']')
        }else if len(stack) == 0 || stack[len(stack)-1] != s[i]{
            return false
        }else{
            stack = stack[:len(stack)-1]
        }
    }
    return len(stack) == 0
}

1190. 反转每对括号间的子串 中等

给出一个字符串 s（仅含有小写英文字母和括号）。

请你按照从括号内到外的顺序，逐层反转每对匹配括号中的字符串，并返回最终的结果。

示例 1：
输入：s = “(abcd)”
输出：”dcba”

示例 2：
输入：s = “(u(love)i)”
输出：”iloveu”
解释：先反转子字符串 “love” ，然后反转整个字符串。

示例 3：
输入：s = “(ed(et(oc))el)”
输出：”leetcode”
解释：先反转子字符串 “oc” ，接着反转 “etco” ，然后反转整个字符串。

示例 4：
输入：s = “a(bcdefghijkl(mno)p)q”
输出：”apmnolkjihgfedcbq”

提示：

• 0 <= s.length <= 2000
• s 中只有小写英文字母和括号
• 题目测试用例确保所有括号都是成对出现的

题解概要：

1.创建一个放字符串的栈, 以及一个保存当前字符的变量
2.遇到 ( 就将当前的字符串推入栈, 并将当前字符串其设置为空
3.遇到 ) 就将当前的字符串反转, 然后与栈的顶部元素合并, 将栈的顶部元素弹出
4.遇到普通的字符就将其添加到当前字符串的尾部
5.遍历结束返回字符串
动画：
点击查看【bilibili】
代码：

func reverseParentheses(s string) string {
    stack := [][]byte{}
    str := []byte{}
    for i,_ := range s{
        if s[i] == '('{
            stack = append(stack,str)
            str = []byte{}
        }else if s[i] == ')'{
            str = reverse(str)
            str = append(stack[len(stack)-1],str...)
            stack = stack[:len(stack)-1]
        }else{
            str = append(str,s[i])
        }
    } 
    return string(str)
}
func reverse(str []byte)[]byte{
    i := 0
    j := len(str)-1
    for i < j{
        temp := str[i]
        str[i] = str[j]
        str[j] = temp
        i++
        j--
    } 
    return str
}

394. 字符串解码 中等

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例 1：
输入：s = “3[a]2[bc]”
输出：”aaabcbc”

示例 2：
输入：s = “3[a2[c]]”
输出：”accaccacc”

示例 3：
输入：s = “2[abc]3[cd]ef”
输出：”abcabccdcdcdef”

示例 4：
输入：s = “abc3[cd]xyz”
输出：”abccdcdcdxyz”

题解概要：

1.构建辅助栈 stack， 遍历字符串 s 中每个字符 c；
当 c 为数字时，将数字字符转化为数字 multi，用于后续倍数计算；
当 c 为字母时，在 res 尾部添加 c；
当 c 为 [ 时，将当前 multi 和 res 入栈，并分别置空置 00：
记录此 [ 前的临时结果 res 至栈，用于发现对应] 后的拼接操作；
记录此 [ 前的倍数 multi 至栈，用于发现对应 ] 后，获取 multi × […] 字符串。
进入到新 [ 后，res 和 multi 重新记录。
当 c 为 ] 时，stack 出栈，拼接字符串 res = last_res + cur_multi * res，其中:+

last_res是上个 [ 到当前 [ 的字符串，例如 “3[a2[c]]” 中的 a；
cur_multi是当前 [ 到 ] 内字符串的重复倍数，例如 “3[a2[c]]” 中的 2。
2.返回字符串 res。

注意：
可将两个栈合为一个栈。
笔者主用go刷题，在go中，字符是 []byte数组。一个栈可读性较差，故使用两个栈。

代码：

import "strconv"
func decodeString(s string) string {
    numStack := []int{}
    strStack := [][]byte{}
    num     := 0
    result  := []byte{}
    for i,_ := range s{
        if '0' <= s[i] && s[i] <= '9'{
            n,_ := strconv.Atoi(string(s[i]))
            num = num*10 + n 
        }else if s[i] == '['{
            numStack = append(numStack,num)
            num = 0
            strStack = append(strStack,result)
            result = []byte{}
        }else if s[i] == ']'{
            count := numStack[len(numStack)-1]
            numStack = numStack[:len(numStack)-1]
            str := strStack[len(strStack)-1]
            strStack = strStack[:len(strStack)-1]
            temp := []byte{}
            for i:= 0;i<count;i++{
                temp = append(temp,result...)
            }
            result = append(str,temp...)
        }else{
            result = append(result,s[i])
        }
    }
    return string(result)
}

678. 有效的括号字符串 中等

给定一个只包含三种字符的字符串：（ ，） 和 *，写一个函数来检验这个字符串是否为有效字符串。有效字符串具有如下规则：

任何左括号 ( 必须有相应的右括号 )。
任何右括号 ) 必须有相应的左括号 ( 。
左括号 ( 必须在对应的右括号之前 )。
* 可以被视为单个右括号 ) ，或单个左括号 ( ，或一个空字符串。
一个空字符串也被视为有效字符串。

示例 1:
输入: “()”
输出: True

示例 2:
输入: “(*)”
输出: True

示例 3:
输入: “(*))”
输出: True

提示：
1.字符串大小将在 [1，100] 范围内。

题解概要：

1.使用两个栈，一个入(，一个入。
2.遇到）则优先用左括号匹配，如果不存在左括号再用号匹配。
3.当遍历完成后，再把当成右括号和（进行匹配，如果没有号出现在（之前，并且最后（栈中不存在元素，说明符合条件。

代码：

func checkValidString(s string) bool {
    starStack := []int{}
    leftStack := []int{}
    for i,v := range s{
        if v == '*'{
            starStack = append(starStack,i)
        }else if v == '('{
            leftStack = append(leftStack,i)
        }else{
            if len(starStack) == 0 && len(leftStack) == 0{
                return false
            }
            if len(leftStack) > 0{
                leftStack = leftStack[:len(leftStack)-1]
                continue
            }
            starStack = starStack[:len(starStack)-1]
        }
    }
    i := len(leftStack)-1
    j := len(starStack)-1
    for i >= 0 && j >= 0{
        if starStack[j] < leftStack[i]{
            return false
        }
        i --
        j --
    }
    return i < 0
}

5. 栈-计算器题目必须 掌握

150. 逆波兰表达式求值 中等

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。
根据 逆波兰表示法，求表达式的值。
有效的算符包括 +、-、*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

示例 1：
输入：tokens = [“2”,”1”,”+”,”3”,”“]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) 3) = 9

题解概要：

标准的栈操作，可参考动画。
点击查看【bilibili】

代码：

import "strconv"
func evalRPN(tokens []string) int {
    stack := []int{}
    for _,v := range tokens{
        if v == "+" {
            num1 := stack[len(stack)-1]
            num2 := stack[len(stack)-2]
            stack[len(stack)-2] = num2 + num1
            stack = stack[:len(stack)-1]
        }else if v == "-" {
            num1 := stack[len(stack)-1]
            num2 := stack[len(stack)-2]
            stack[len(stack)-2] = num2 - num1
            stack = stack[:len(stack)-1]
        }else if v == "*" {
            num1 := stack[len(stack)-1]
            num2 := stack[len(stack)-2]
            stack[len(stack)-2] = num2 * num1
            stack = stack[:len(stack)-1]
        }else if v == "/" {
            num1 := stack[len(stack)-1]
            num2 := stack[len(stack)-2]
            stack[len(stack)-2] = num2 / num1
            stack = stack[:len(stack)-1]
        }else{
            tmp, _ := strconv.Atoi(v)
            stack = append(stack,tmp)
        }
    }
    return stack[0]
}

227. 基本计算器 II 中等

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。
整数除法仅保留整数部分。

示例 1：
输入：s = “3+2*2”
输出：7

示例 2：
输入：s = “ 3/2 “
输出：1

示例 3：
输入：s = “ 3+5 / 2 “
输出：5

提示：
1 <= s.length <= 3 105
s 由整数和算符 (‘+’, ‘-‘, ‘‘, ‘/‘) 组成，中间由一些空格隔开
s 表示一个 有效表达式
表达式中的所有整数都是非负整数，且在范围 [0, 231 - 1] 内
题目数据保证答案是一个 32-bit 整数

题解概要：

1. 定义 num 储存数字，定义oper 存储上一步操作符。

   1. 遇到 + ，将num入栈；遇到 - ，将 -num 入栈。
      3. 遇到 * ，将栈顶元素出栈与num相乘，最后将乘积入栈。
      4. 遇到 / , 将栈顶元素出栈与num相除，最后将结果入栈。
      5. 最后，将栈中结果相加，即为所求结果。

注意：
本题需要注意边界条件，由于都是遇到下一操作符，才会计算上一表达式的值，所以当遍历到最后一个元素时，要对上一表达式进行计算。

例如：在”3 22” 这一表达式中，当遍历到第二个时，才会对32这一表达式进行计算。

代码：

func calculate(s string) int {
    stack := []int{}
    oper := '+'
    num := 0
    for i,ch := range s{
        isdight := '0' <= ch && ch <= '9'
        if isdight{
            num = num*10 + int(ch-'0')    //数字有可能是多位数
        }
        if !isdight && ch != ' ' || i == len(s)-1{ //注意len(s)-1边界条件。
            switch oper{
            case '+':
                stack = append(stack,num)
            case '-':
                stack = append(stack,-num)
            case '*':
                //获取栈顶元素
                top := stack[len(stack)-1]
                stack[len(stack)-1] = top * num
            case '/':
                //获取栈顶元素
                top := stack[len(stack)-1]
                stack[len(stack)-1] = top / num
            }
            num = 0
            oper = ch
        }
    }
    ans := 0
    for _,v := range stack{
        ans += v
    }
    return ans
}

224. 基本计算器 困难

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

示例 1：
输入：s = “1 + 1”
输出：2

示例 2：
输入：s = “ 2-1 + 2 “
输出：3

示例 3：
输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

提示：
1 <= s.length <= 3 * 105
s 由数字、’+’、’-‘、’(‘、’)’、和 ‘ ‘ 组成
s 表示一个有效的表达式

题解概要：

res 表示左边表达式除去栈内保存元素的计算结果；
sign 表示运算符；
num 表示当前遇到的数字，会更新到 res 中；
用栈保存遇到左括号时前面计算好了的结果和运算符。
操作的步骤是：
如果当前是数字，那么更新计算当前数字；
如果当前是操作符+或者-，那么需要更新计算当前计算的结果 res，并把当前数字 num 设为 0，sign 设为正负，重新开始；
如果当前是 ( ，那么说明遇到了右边的表达式，而后面的小括号里的内容需要优先计算，所以要把 res，sign 进栈，更新 res 和 sign 为新的开始；
如果当前是 ) ，那么说明右边的表达式结束，即当前括号里的内容已经计算完毕，所以要把之前的结果出栈，然后计算整个式子的结果；
最后，当所有数字结束的时候，需要把最后的一个 num 也更新到 res 中。

大佬题解：
https://leetcode-cn.com/problems/basic-calculator/solution/ru-he-xiang-dao-yong-zhan-si-lu-lai-zi-y-gpca/

代码：

func calculate(s string) int {
    stack := [][]int{} //使用二维数组，数组的第一位存数字，第二位存符号(-1 或 1)。
    sign := 1  //符号位。
    num  := 0  //记录数字
    ans  := 0  //结果
    for _,ch := range s{
        if '0' <= ch && ch <= '9'{
            num = num *10 + int(ch-'0')
        }else if ch == '+' || ch =='-'{
            ans += sign * num   //计算上一表达式
            num = 0             //将num设置为0
            //记录操作符
            if ch == '-'{
                sign = -1
            }else{
                sign = 1
            }
        }else if ch == '('{
            //遇到 (,则先将 sign与res 推入栈,等)时再推出来。
            stack = append(stack,[]int{ans,sign})
            //将sign设置为1
            sign = 1  //将操作符还原为0
            ans = 0   //因为ans暂放到栈中了，因此要将ans存为0
        }else if ch == ')'{
            //遇到)时，首先计算)内res的值
            ans += sign * num
            num = 0
            sign = 1
            //再将之前的值与括号内的值进行计算
            top := stack[len(stack)-1]
            ans *= top[1]
            ans += top[0]
            stack = stack[:len(stack)-1] 
        }
    }
    ans += sign * num  //因为是遇到 操作符时才会计算前一表达式的值， 例如"2+1" 这个等式，当遍历到最后一位1时，就结束了，因此要在这里再计算一次。
    return ans
}

1006. 笨阶乘 中等

通常，正整数 n 的阶乘是所有小于或等于 n 的正整数的乘积。例如，factorial(10) = 10 9 8 7 6 5 4 3 2 * 1。

相反，我们设计了一个笨阶乘 clumsy：在整数的递减序列中，我们以一个固定顺序的操作符序列来依次替换原有的乘法操作符：乘法(*)，除法(/)，加法(+)和减法(-)。

例如，clumsy(10) = 10 9 / 8 + 7 - 6 5 / 4 + 3 - 2 * 1。然而，这些运算仍然使用通常的算术运算顺序：我们在任何加、减步骤之前执行所有的乘法和除法步骤，并且按从左到右处理乘法和除法步骤。

另外，我们使用的除法是地板除法（floor division），所以 10 * 9 / 8 等于 11。这保证结果是一个整数。

实现上面定义的笨函数：给定一个整数 N，它返回 N 的笨阶乘。

示例 1：
输入：4
输出：7
解释：7 = 4 * 3 / 2 + 1

示例 2：
输入：10
输出：12
解释：12 = 10 9 / 8 + 7 - 6 5 / 4 + 3 - 2 1

*提示：
1 <= N <= 10000
-2^31 <= answer <= 2^31 - 1 （答案保证符合 32 位整数。）

题解概要：

1.本题和227.基本计算器 相似，加减乘除的计算有固定的套路。
2.遇到 *,/ 将计算后的结果赋值给栈顶，遇到+，- 将计算后的结果入栈。
3.最后将栈中数据相加，就是所求结果。

图解：

代码：

func clumsy(n int) int {
    stack := []int{n}
    n -- 
    index := 0 
    for n > 0 {
        switch index%4{
            case 0:
                top := len(stack)-1
                stack[top] *= n
            case 1:
                top := len(stack)-1
                stack[top] /= n
            case 2:
                stack = append(stack,n)
            case 3:
                stack = append(stack,-n)
        }
        index ++ 
        n--
    }
    ans := 0 
    for _,v := range stack{
        ans += v
    }
    return ans
}

6. 栈-直方图题目必须 掌握

739. 每日温度 中等

请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]

示例 2:
输入: temperatures = [30,40,50,60]
输出: [1,1,1,0]
请根据每日 气温 列表 temperatures ，请计算在每一天需要等几天才会有更高的温度。如果气温在这之后都不会升高，请在该位置用 0 来代替。

示例 3:
输入: temperatures = [30,60,90]
输出: [1,1,0]

提示：
1 <= temperatures.length <= 105
30 <= temperatures[i] <= 100

题解概要：

1.遍历整个数组，如果栈不空，且当前数字大于栈顶元素，那么如果直接入栈的话就不是 递减栈 ，所以需要取出栈顶元素，由于当前数字大于栈顶元素的数字，而且一定是第一个大于栈顶元素的数，直接求出下标差就是二者的距离。

2.继续看新的栈顶元素，直到当前数字小于等于栈顶元素停止，然后将数字入栈，这样就可以一直保持递减栈，且每个数字和第一个大于它的数的距离也可以算出来。

代码：

func dailyTemperatures(temperatures []int) []int {
    stack := []int{}    //单调递减队列
    res := make([]int,len(temperatures))    
    for i,_ := range temperatures{
        //维护单调递减队列
        for len(stack) != 0 && temperatures[i] > temperatures[stack[len(stack)-1]]{
            index :=  stack[len(stack)-1]
            res[index] = i - index
            stack = stack[:len(stack)-1]
        }
        stack = append(stack,i)
    }
    return res
}

42. 接雨水 困难

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

示例 1：
输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

提示：

• n == height.length
• 0 <= n <= 3 * 104
• 0 <= height[i] <= 105

题解概要：

1.根据提议，我们知道当遇到”凹地”时可接到雨水。因此，需要一个单调递减栈，当遇到比栈顶要大的元素时，栈顶元素为凹地所接的雨水量就可以算出来了。

例如：1,0,2所表示的凹地雨水量是1，如何计算呢？
0的索引是2,1的索引是1,2的索引是3。
凹地的宽度 = 3-1-1 = 1 （凹地右侧索引-凹地左侧索引-1）
凹地的高度 = (1-0) = 1 (凹地左右两次中最小的那一侧 - 凹地最底部的高度)

点击查看【bilibili】
代码：

func trap(height []int) int {
    stack := []int{} //存索引
    ans := 0 //存雨水量
    for i,v := range height{
        for len(stack) != 0 && v > height[stack[len(stack)-1]]{
            top := stack[len(stack)-1]     //获取栈顶元素（凹的最低值）
            stack = stack[:len(stack)-1]   //模拟栈行为,将栈顶元素弹出
            for len(stack) > 0 && top == stack[len(stack)-1]{
                 stack = stack[:len(stack)-1]   //模拟栈行为,将栈顶元素弹出
            }
            if len(stack) > 0 {
                left := stack[len(stack)-1]
                right := i
                height := min(height[left]-height[top],height[right]-height[top])
                ans += height * (right-left-1)
            }  
        }
        stack = append(stack,i)
    }
    return ans
}
func min(a int,b int)int{
    if a > b {
        return b
    }
    return a
}

84. 柱状图中最大的矩形 困难

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

求在该柱状图中，能够勾勒出来的矩形的最大面积。

示例 1:

输入：heights = [2,1,5,6,2,3]
输出：10
解释：最大的矩形为图中红色区域，面积为 10

提示：

• 1 <= heights.length <=105
• 0 <= heights[i] <= 104

题解概要：

1.维护一个单调递增的栈。
2.为了方便计算需要在头部与尾部增加两个元素。
3.可以参考下方题解，讲的非常好。

大佬题解：
https://leetcode-cn.com/problems/largest-rectangle-in-histogram/solution/dong-hua-yan-shi-dan-diao-zhan-84zhu-zhu-03w3/

代码：

func largestRectangleArea(heights []int) int {
    stack := []int{-1} //存入的应该是索引
    ans := 0
    heights = append(heights,0) //尾部加0方便计算。
    for i,v := range heights{
        //小于时，出栈，计算高度
        for len(stack) >0 && stack[len(stack)-1] != -1 && v < heights[stack[len(stack)-1]]{
            left := stack[len(stack)-2]
            right := i
            height := heights[stack[len(stack)-1]]
            area := (right-left-1) * height        
            ans = max(ans,area)
            stack = stack[:len(stack)-1]
        }
        stack = append(stack,i)
    }
    return ans
}
func max (a int,b int)int{
    if a>b{
        return a
    }
    return b
}

7. 栈-其他题目必须 掌握

1047. 删除字符串中的所有相邻重复项 简单

给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

示例：
输入：”abbaca”
输出：”ca”
解释：
例如，在 “abbaca” 中，我们可以删除 “bb” 由于两字母相邻且相同，这是此时唯一可以执行删除操作的重复项。之后我们得到字符串 “aaca”，其中又只有 “aa” 可以执行重复项删除操作，所以最后的字符串为 “ca”。

提示：
1 <= S.length <= 20000
S 仅由小写英文字母组成。

题解概要：

1.标准的栈操作。遍历字符串，若当前字符与栈顶相同，则栈顶元素出栈。若不相同，入栈。
2.最后，栈中剩余元素即为所求值。

代码：

func removeDuplicates(s string) string {
    stack := []rune{}
    for _,ch := range s{
        if len(stack)!=0 && stack[len(stack)-1] == ch{
            stack = stack[:len(stack)-1]
            continue
        }
        stack = append(stack,ch) 
    }
    return string(stack)
}