栈
当前位置的元素不能立刻计算,需要隔着一段距离去找另一个对应的元素。
单调栈问题:
42.接雨水 (hard)
当不能继续维持单调递减栈时,就证明能存贮水,那么把无法继续保持递减的部分出栈,并算出由出栈部分与当前高度的差值所能贮存的水量。关键是确定当前位置积水量的方法是,在当前位置两侧比当前位置高的元素。
84.柱状图中矩形最大面积 (hard)
如果能维持递增的关系,那么包含当前柱子的最大矩形就还不能确定,因为如果右边更大就可以继续往右侧扩展,而如果无法保持递增,那么当前柱子小于上个柱子的高度。以上个柱子为高度的矩形面积就可以确定下来了。此时出栈无法保持递增栈的柱子(即面积已经确定的成员)并对其面积进行计算。关键是确定以当前柱子为高度的矩形所需要找到当前柱子两侧更矮的柱子。
739.每日温度(medium)
从后向前遍历,因为需要找后方比当前位置温度高的元素,因此维护一个从后向前的递增栈即可。
找右边方向比当前大的元素
利用栈代替递归:
105.用栈实现二叉树的几种遍历(medium)
这里是利用栈去代替递归操作
括号类问题:
32.最长有效括号(hard)
能够找到匹配对象则出栈,最后计算匹配出栈时的距离。
394.字符串解码(medium)
由于括号的生长方式一般是由内向外的,在利用栈进行操作时根据括号的匹配情况能找到最内侧的括号,并根据匹配的情况依次出栈相应成员。本题目由于会涉及到括号外部的multi乘积,所以需要独立为表示次数的数字建立栈。数字先入栈稍后再根据嵌套情况做处理。
队列
102.层序遍历二叉树(medium)
利用队列的先进先出次序完成对树每层的遍历
双端队列:
239.滑动窗口最大值(hard)
需要从两侧pop元素,当向队列中加入新的值时,如果队列中有数值小于当前值,那么证明在窗口内小于当前值的数字不再起作用就从后方将其pop出来。当队列中元素的个数超过了窗口的长度时则需要从队列前端pop掉旧的元素。因此需要用到双端队列来模拟滑动窗口的过程。
优先队列:
利用大根堆小根堆进行排序
347.前k个高频元素(medium)
实际上是利用优先队列内部实现是堆的这一特性,利用它进行一个快速的排序。可以指定以结构体中的哪个元素为参考进行排序,默认情况下是利用大根堆进行自动排序,若需要小根堆则需要指定priority_queue<<int>,vector<int>,greater<int>> q;
1353.最多可以参加的会议数目(medium)
这道题目是典型的贪心算法,先参加当前情况下结束最早的会议,此处是利用小根堆排序以较小的时间复杂度来获得当前结束时间最早的会议。