理解：

单调栈和单调队列，其实就是里面存储的元素是单调递增或递减的栈和队列，它们的核心思想都是在一些遍历问题中，舍弃一些不必要的元素，只保留可能有用的元素，使得之后遍历时能越过那些不必要元素以节省时间；下面两道题可以说明是怎么“舍弃”和“保留”元素的；

单调栈：

对于这道题：

https://leetcode-cn.com/problems/next-greater-element-ii/
给定一个循环数组（最后一个元素的下一个元素是数组的第一个元素），输出每个元素的下一个更大元素。数字 x 的下一个更大的元素是按数组遍历顺序，这个数字之后的第一个比它更大的数，这意味着你应该循环地搜索它的下一个更大的数。如果不存在，则输出 -1。

示例 1:

输入: [1,2,1]
输出: [2,-1,2]
解释: 第一个 1 的下一个更大的数是 2；
数字 2 找不到下一个更大的数；
第二个 1 的下一个最大的数需要循环搜索，结果也是 2。

我们当然可以通过遍历解决这个问题（从元素当前位置一直遍历到数组末尾，直到找到比当前元素大的元素），但我们也可以使用单调栈来减少时间复杂度，从数组最后位置向前遍历并将当前下标位置的元素入栈。每次入栈时，先将栈中比即将要入栈的元素小的元素全部取出，为什么要这么做呢？因为这些被取出的元素必不可能成为后续元素的“下一个更大元素”；

例子：对于数组[9,3,7,4,8]；
当前元素为8，8入栈，当前栈[8]；由于8入栈时，栈为空，所以8的“下一个更大元素”为-1（即没有下一个更大元素）；

当前元素为4，栈顶元素8比4大，4直接入栈，当前栈[4,8]，所以4的“下一个更大元素”为栈顶元素8；

当前元素为7，7比栈顶元素4大，4出栈，（因为即将要变成栈顶的元素是7,在数组中4的下标在7的后面，于是7之前的元素，也就是9,3，其下一个最大元素要么是7（7比起4，距离9,3更近，同时7也比4要大），要么是4后面的可能比7更大的数（例如9，7也顶不住9，但是7后面的元素有可能比9大），总之，4不可能是剩下元素的解了，因此直接把它拿出来）；当前栈[7,8]，所以7的“下一个更大元素”为栈顶元素8；
…

这样就保证了，栈中所存储的内容，永远是可能成为后续解的元素所组成的一个递增序列，在每次入栈时，取出一些根据当前判断，已经不可能成为后续解的元素，防止之后在寻找“下一个最大元素”途中，花多余的时间跟这些元素比较。

单调队列

单调队列跟单调栈类似，也是在遍历途中，不断排除一些多余元素，为后续查找省下时间；

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
给定一个数组 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

在每次找当前窗口的最大元素时，自然可以使用遍历，但是耗时长，那么我们可以尝试跟上道题目一样的办法，在窗口滑动时，排除掉一些不可能成为后续答案的元素，减少后续时间消耗；

与上题不同的是，这道题中元素的界限是变化的，即使当前元素很大，可能会成为后续答案，但是也会因窗口的移动而失效，倘若使用栈，那我们可能需要每次移动时，从栈底删除当前已经不在窗口中的元素，
我们使用队列来完成这一操作，虽然是队列，其实跟上题的栈结构相似，也可以看成特殊的栈，不过我们需要对栈底元素进行一些操作：在加入新元素时，先移除所有比他小的栈顶元素，之后获取当前窗口最大值，也就是栈底元素，然后，判断需不需要移除栈底元素（窗口每滑动一次，末尾就会有一个元素失效，当前栈底元素可能是这个失效元素，也有可能不是，因为这个失效元素可能早就在其他元素入栈时被移除掉了）

    public int[] maxSlidingWindow(int[] nums, int k) {if(nums.length==0){return new int[0];}int[] res = new int[nums.length+1-k];for(int i = 0 ; i<nums.length;i++){if(i<k-1){queue_push(nums[i]);}else{queue_push(nums[i]);res[i-k+1] = queue_getmax();queue_pop(nums[i-k+1]);}}return res;}Deque<Integer> queue = new LinkedList<Integer>();//在每次入队列时，先取出队尾（类似于上题的栈顶）比它小的元素public void queue_push(int i){while(!queue.isEmpty()&&queue.peekLast()<i){queue.pollLast();}queue.offer(i);}//得到当前窗口最大元素，也就是队列头（类似于上题的栈底）的元素public Integer queue_getmax(){return queue.peek();}//尝试移除被窗口抛弃的元素（当然被窗口抛弃的元素可能早就在之前queue_push中被移除了）public void queue_pop(int i){if(i==queue.peek()){queue.poll();}}