知识点

1. 知识点
   1. 单调栈
      单调栈是栈这种数据结构的强化，可以保证新元素入栈后，栈内的元素都保持有序（单调递增或单调递减）

LeetCode算法题

1. LeetCode算法题

   1. 295.【数据流的中位数】

      解题思路：

      数据流的数据结构，底层需要保证数据有序的容器，同时，保证增删改查的时间复杂度都较低。因此，底层不能使用数组和链表，同时因为TreeSet不允许重复元素并且没有快速根据排名计算元素的api(因为如果元素个数为偶数，中位数是计算出来的)所以不能使用，优先级队列只能在堆顶添加/删除元素findMedian方法需要在中间取值无法满足也不能使用。

      因此，一个基本容器无法满足，我们可以使用两个容器，两个优先级队列，一个大顶堆，一个小顶堆来实现。大顶堆存小的那一半的元素，小顶堆存储大的一半元素，因此添加/删除元素根据堆特性时间复杂度很低，findMeidan方法通过查看两个堆堆顶的元素即可直接返回或计算，满足所有要求。

   2. 496.【下一个更大元素I】

      解题思路：利用单调栈。我们定义一个栈，该栈单调递增；将数组2从后向前遍历，然后压入单调栈，对于数组2中的第i个元素来说，栈中如果有元素，则栈顶元素就是i对应的第一个更大元素；利用HashMap记录元素i和对应更大元素的关系，没有更大元素记录为-1；遍历数组1，从HashMap中获取结果集。

   3. 1118.【一月有多少天】

      解题思路：也是利用单调栈来解决问题，不过因为题目要求的是两个天数之间的间隔，因此单调栈虽然通过温度来进行单调，但是存储要存储索引，用来计算间隔。

   4. 503.【下一个更大元素II】

      解题思路：该问题还是要使用单调栈来解决，但是如何让后边的环绕一圈来寻找呢？一般这种问题，我们将数组翻倍，即可解决环绕一圈寻找的问题。不必创建新的长度翻倍数组，我们可以使用循环数组的技巧，使用翻倍索引+Mod运算即可。