双端单调队列与单调栈
双端单调队列（滑动窗口问题）
- 基本概念：窗口（在数组的基础上）
（1）有一个L为左边界，R为右边界，初始均在数组的最左侧
（2）移动时：L或R只能往右移动
（3）L始终要在R的左侧
（4）R往右移动元素入窗口，L右移动元素出窗口 - 要求：在极小的代价（小于遍历窗口的代价）的情况下，每次用户改变窗口都能得到窗口的最大值或最小值
- 解决方法：双端队列
（1）双端队列中存入数组的下标，（通过下标即可以访问元素，也可以确定其在数组中的位置，在实现代码时方便操作）
（2）假设求最大值，头 ——> 尾 （最大值 ——> 最小值）
（3）R移动，元素从队尾入队，入队前判断是否满足大——>小的单调关系，若满足直接入队，若不满足，将 <= 该元素的值全部出队（且不需要再次添加入队）
（4）L移动，只需看头部节点目前是否在窗口中，若不在，直接从头部出队，若在，无需操作
（5）双端队列维持信息：在对头始终可以提供窗口的最大值 - 时间复杂度分析：双端队列的维持整个遍历数组为O(N)，一次移动窗口就是O(N) / N = O(1)，N为数组的长度
- 代码实现：
public static class WindowMax{ //窗口类 private int L; //左右边界 private int R; private int[] arr; //原始数组 private LinkedList<Integer> queue; //双端队列 public WindowMax(int[] arr){ this.arr = arr; L = -1; R = -1; queue = new LinkedList<>(); } public void addNum(){ //R移动 if (R == arr.length - 1){ return; } R++; while (!queue.isEmpty() && arr[queue.peekLast()] <= arr[R]){ //不满足单调队列，队列的尾出队 queue.pollLast(); } //入队 queue.addLast(R); } public void removeNum(){ //L移动 if (L >= R - 1){ //L始终要在R的右边 return; } L++; if (queue.peekFirst() == L){ //判断对头是否需要出队 queue.pollFirst(); } } public Integer getMax(){ //得到最大值 if (!queue.isEmpty()){ //双端队列不为空，直接返回对头 return arr[queue.peekFirst()]; } return null; } }
- 例题：
public static int[] getWindowMax(int[] arr, int w){ if (arr == null || w < 1 || arr.length < w){ return null; } LinkedList<Integer> queue = new LinkedList<Integer>(); //双端队列 int[] res = new int[arr.length - w + 1]; int index = 0; //res数组中的位置 for (int i = 0; i < arr.length; i++){ //遍历数组 //i就是右边界 //i - w就是左边界 while (!queue.isEmpty() && arr[queue.pollLast()] <= arr[i]){ //将不满足双端单调队列队尾的出队，右边界移动时维护双端单调队列 queue.pollLast(); } queue.addLast(i); //右边界移动 if (queue.peekFirst() == i - w){ //不满足队头的出队 //左边界移动 queue.pollFirst(); } if (i >= w - 1){ //窗口形成后开始收集最大值 res[index++] = arr[queue.pollFirst()]; } } return res; }
单调栈
- 问题描述：在一个数组上，要求得到每一个位置上距离该位置最近的左右两边比该位置数值大或者小的
- 常规思路：到达一个位置后，分别左右遍历，寻找，时间复杂度为O（N ^ 2）
- 目标：进行优化将时间复杂度达到 O (N)
- 解决方法：单调栈
（1）单调栈中存入数组的下标，（通过下标即可以访问元素，也可以确定其在数组中的位置，在实现代码时方便操作）
（2）假设求最大值，栈底 ——> 栈顶 （最大值 ——> 最小值），最小只需变为，栈底 ——> 栈顶（最小值 ——> 最大值）
（3）遍历数组，满足单调栈的直接入栈，若不满足，将不满足的元素依次弹出
（4）弹出元素的最大值信息就可以得到：其左边较大，原栈中该元素下面紧邻的元素（目前的栈顶元素）；右边较大，当前使该元素出栈的元素，若没有就是无
（5）遍历完数组后进行栈的处理，全部栈元素出栈，其左边较大，原栈中该元素下面紧邻的元素；右边较大均为无 - 特殊处理：若有相同元素出现，可以将相同的元素压入栈中的同一空间 ：Stack<List< Integer>>即将列表作为一个栈的空间，且添加时，相同元素一定会在栈顶相遇，直接栈顶元素的List添加即可，在实用相同元素确定距离最近的较大值位置，就是列表的最后一个
- 时间复杂度分析：遍历一次便可以得到，时间复杂度为O(N)
- 代码实现：
public static int[][] getNearMore_NoRepeat(int[] arr){ //在无重复的条件下得到每个字符两侧的较大值 int[][] res = new int[arr.length][2]; //只保存对应下标 [][0]:左边，[][]1:右边 Stack<Integer> stack = new Stack<>(); //单调栈 for (int i = 0; i < arr.length; i++){ //遍历数组 while (!stack.isEmpty() && arr[stack.peek()] < arr[i]){ //判断是否出栈的条件 int temp = stack.pop(); //左端较大，若栈为空：无，返回-1；若有返回目前的栈顶 int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek(); res[temp][0] = leftMoreIndex; res[temp][1] = i; } stack.push(i); } while (!stack.isEmpty()){ //数组遍历结束，对栈的处理 int temp = stack.pop(); int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek(); res[temp][0] = leftMoreIndex; //右边均为无，返回-1 res[temp][1] = -1; } return res; }
public static int[][] getNearMore(int[] arr){ //在有重复的条件下得到每个字符两侧的较大值 int[][] res = new int[arr.length][2]; //只保存对应下标 [][0]:左边，[][]1:右边 Stack<List<Integer>> stack = new Stack<>(); //单调栈 for (int i = 0; i < arr.length; i++){ //遍历数组 while (!stack.isEmpty() && arr[stack.peek().get(0)] < arr[i]){ //判断是否出栈的条件 List<Integer> tempList = stack.pop(); //左端较大，若栈为空：无，返回-1；若有返回目前的栈顶队列的最后一个 int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer temp : tempList){ res[temp][0] = leftMoreIndex; res[temp][1] = i; } } if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) { //相同元素放入栈中的相同队列 stack.peek().add(i); } else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); stack.push(list); } } while (!stack.isEmpty()){ //数组遍历结束，对栈的处理 List<Integer> tempList = stack.pop(); int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer temp : tempList){ res[temp][0] = leftMoreIndex; res[temp][1] = -1; } } return res; }
public static int[][] getNearLess_NoRepeat(int[] arr){ //在无重复的条件下得到每个字符两侧的较小值 int[][] res = new int[arr.length][2]; //只保存对应下标 [][0]:左边，[][]1:右边 Stack<Integer> stack = new Stack<>(); //单调栈 for (int i = 0; i < arr.length; i++){ //遍历数组 while (!stack.isEmpty() && arr[stack.peek()] > arr[i]){ //判断是否出栈的条件 int temp = stack.pop(); //左端较大，若栈为空：无，返回-1；若有返回目前的栈顶 int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek(); res[temp][0] = leftMoreIndex; res[temp][1] = i; } stack.push(i); } while (!stack.isEmpty()){ //数组遍历结束，对栈的处理 int temp = stack.pop(); int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek(); res[temp][0] = leftMoreIndex; //右边均为无，返回-1 res[temp][1] = -1; } return res; }
public static int[][] getNearLess_NoRepeat(int[] arr){ //在无重复的条件下得到每个字符两侧的较小值 int[][] res = new int[arr.length][2]; //只保存对应下标 [][0]:左边，[][]1:右边 Stack<Integer> stack = new Stack<>(); //单调栈 for (int i = 0; i < arr.length; i++){ //遍历数组 while (!stack.isEmpty() && arr[stack.peek()] > arr[i]){ //判断是否出栈的条件 int temp = stack.pop(); //左端较大，若栈为空：无，返回-1；若有返回目前的栈顶 int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek(); res[temp][0] = leftMoreIndex; res[temp][1] = i; } stack.push(i); } while (!stack.isEmpty()){ //数组遍历结束，对栈的处理 int temp = stack.pop(); int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek(); res[temp][0] = leftMoreIndex; //右边均为无，返回-1 res[temp][1] = -1; } return res; } public static int[][] getNearLess(int[] arr){ //在有重复的条件下得到每个字符两侧的较小值 int[][] res = new int[arr.length][2]; //只保存对应下标 [][0]:左边，[][]1:右边 Stack<List<Integer>> stack = new Stack<>(); //单调栈 for (int i = 0; i < arr.length; i++){ //遍历数组 while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]){ //判断是否出栈的条件 List<Integer> tempList = stack.pop(); //左端较大，若栈为空：无，返回-1；若有返回目前的栈顶队列的最后一个 int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer temp : tempList){ res[temp][0] = leftMoreIndex; res[temp][1] = i; } } if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) { //相同元素放入栈中的相同队列 stack.peek().add(i); } else { ArrayList<Integer> list = new ArrayList<>(); list.add(i); stack.push(list); } } while (!stack.isEmpty()){ //数组遍历结束，对栈的处理 List<Integer> tempList = stack.pop(); int leftMoreIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer temp : tempList){ res[temp][0] = leftMoreIndex; res[temp][1] = -1; } } return res; }
- 例题：
例：[5, 3, 2, 4, 6, 1, 7 ,9 ,8]
若选择5 确定的数组为[5]
若选择2 确定的数组为[2]，[3，2]，[5，3，2]，[2，4]，[2，4，6]……[5, 3, 2, 4, 6]
若选择1 确定的数组为[1]，[6,1]，[4,6,1]……[5, 3, 2, 4, 6, 1, 7 ,9 ,8] - 难点：使用常规思路（枚举法）子数组过多，时间复杂度极高
- 分析：本题看似于单调栈无关，其实：每一个数作为最小值，其对应的子数组最长时就是求A的时刻，实际上可以利用单调栈求两侧最小值的办法，进行确定每一个数作为最小值时，快速确定其对应的最长子数组
- 常规思路：枚举法（暴力求解），遍历出所有的子数组，得到所有子数组的累加和，最小值，求出对应的A
public static int getMaxA(int[] arr){ int maxA = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++){ for (int j = i; j < arr.length; j++){ //遍历所有子数组 [i……j] int minNum = Integer.MAX_VALUE; //子数组的最小值 int sum = 0; //子数组的和 for (int index = i; index <= j; index++){ //子数组中求和与最小值 sum += arr[index]; minNum = Math.min(minNum, arr[index]); } maxA = Math.max(maxA, sum * minNum); } } return maxA; }
时间复杂度：O(N^3)
- 单调栈的使用思路：在常规思路的基础上优化，利用两侧找最小，确定每一个数作为最小值时，其对应的最长子数组，节省大量求子数组的时间
（1）先求出从最左到右，每个位置的和存入sums[]
（2）建立单调栈，栈底 ——> 栈顶（最小值 ——> 最大值）
（3）当满足单调栈的条件直接入栈
（4）若不满足出栈，此时便能直接求出该出栈元素的A值，最小值：就是当前出栈元素对应数组中的元素，sum：使其出栈的元素时比其小则可以提供R，其在目前栈顶的元素也比起小可以提供L；若栈为空了，那么L就是数组的最左端
（5）当数组遍历完，栈仍然不为空，那么R就是数组的最右端，L依旧使用栈顶方法寻找
（6）小技巧：sums[]数组的存在，sum[L，R] = sums[ R ] - sums[ L ]，无需在遍历子数组求sum
public static int getMaxA(int[] arr){ int size = arr.length; int[] sums = new int[size]; sums[0] = arr[0]; for (int i = 1; i < size; i++) { //记录从左到右每个位置的和 sums[i] = sums[i - 1] + arr[i]; } int max = Integer.MIN_VALUE; Stack<Integer> stack = new Stack<Integer>(); //单调栈 for (int i = 0; i < size; i++) { //遍历数组 while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) { //满足出栈的条件，该元素就是最小值，找其对应的最长子数组 int minNumIndex = stack.pop(); //sum[L，R] = sums[R] - sum[L] //栈为空，L = 0 int sum = stack.isEmpty() ? sums[i - 1] : (sums[i - 1] - sums[stack.peek()]); max = Math.max(max, sum * minNumIndex); } stack.push(i); } while (!stack.isEmpty()) { //数组遍历结束，处理栈中剩余 int minNumIndex = stack.pop(); //R为最右端，R = size - 1 int sum = stack.isEmpty() ? sums[size - 1] : (sums[size - 1] - sums[stack.peek()]); max = Math.max(max, sum * minNumIndex); } return max; }
时间复杂度O（N)
总结
- 双端单调队列：可以用来求滑动窗口的最值问题
- 单调栈：可以用来求数组中每一个数字作为最小值（求得到每一个位置上距离该位置最近的左右两边比该位置数值小的），或者作为最大值（求得到每一个位置上距离该位置最近的左右两边比该位置数值大的）时其最长子数组
