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

悠悠 2022-09-10 03:09 120阅读 0赞

## 最大值窗口 ##

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；即窗口的最右边的idx
                if (r >= k - 1){
        
                    res[idx++] = nums[deque.peekFirst()];
                }
            }
            return res;
        }
    }

## manacher算法伪代码： ##

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Lqt5Lit54us6YWM_size_20_color_FFFFFF_t_70_g_se_x_16]

## 单调栈： ##

处理下一个最大值问题【 **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++) {
        
    //            进来的数比里面的栈顶元素小，那么就可以开始记录res
                while (!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;
                    }
                }
    //            相等的情况，往栈顶的最后面加自己的index
                if (!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;
        }
    }

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA5Lqt5Lit54us6YWM_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/6e90d8228c094a46b07f514b17bb891a.png