左神说：被火车撞了都不能忘记的算法

本文主要是介绍左神说：被火车撞了都不能忘记的算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

最大值窗口

https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/

class Solution {public int[] maxSlidingWindow(int[] nums, int k) {if(nums == null || k < 1 || nums.length<k) return new int[]{};int[] res = new int[nums.length - k + 1];LinkedList<Integer> deque = new LinkedList<>();int idx =0;for (int r = 0; r < nums.length; r++) {// 如果双端队列为空 or 最后一个数字<=当前的值都跳出去while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[r]) {deque.pollLast();}deque.addLast(r);// r-k到了第5个数，2肯定是过期的r-k刚好是当前窗口的左边一个值if (deque.peekFirst() == r-k) {deque.pollFirst();}// 如果r已经到了k-1；即窗口的最右边的idxif (r >= k - 1){res[idx++] = nums[deque.peekFirst()];}}return res;}
}

manacher算法伪代码：

在这里插入图片描述

单调栈：

处理下一个最大值问题【 Next Greater Element 】

    public static int[][] getNearLess(int[] arr) {int[][] res = new int[arr.length][2];Stack<List<Integer>> stack = new Stack<>();for (int i = 0; i < arr.length; i++) {
//            进来的数比里面的栈顶元素小，那么就可以开始记录reswhile (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {List<Integer> popLs = stack.pop();int leftidx = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer popi : popLs) {res[popi][0] = leftidx;res[popi][1] = i;}}
//            相等的情况，往栈顶的最后面加自己的indexif (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {stack.peek().add(Integer.valueOf(i));
//            进来的数字比较大，那么就应该继续往栈顶加} else {ArrayList<Integer> list = new ArrayList<>();list.add(i);stack.push(list);}}
//        逻辑其实和第一段一样，只不过是没有后面元素可以加进去了while (!stack.isEmpty()) {List<Integer> popLs = stack.pop();// 弹出了但是里面还有东西，那就拿出里面的栈顶元素int leftidx = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer popi : popLs) {res[popi][0] = leftidx;res[popi][1] = -1;}}return res;}
}

739. 每日温度

https://leetcode-cn.com/problems/daily-temperatures/

class Solution {public int[] dailyTemperatures(int[] temperatures) {if(temperatures == null) return new int[]{};int[] res = new int[temperatures.length];Stack<Integer> stack = new Stack<>();for (int i = 0; i<temperatures.length; i++) {while (!stack.isEmpty() && temperatures[stack.peek()] < temperatures[i]) {res[stack.peek()] = i - stack.peek();stack.pop();}stack.push(i);}return res;}
}