算法基础提升——滑动窗口、单调栈和单调栈的应用
2022/3/29 17:26:33
本文主要是介绍算法基础提升——滑动窗口、单调栈和单调栈的应用,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
package com.zuoshen.jichutisheng.class04; import java.util.ArrayList; import java.util.Arrays; import java.util.LinkedList; import java.util.Stack; /** * @author ShiZhe * @create 2022-03-28 19:45 */ public class code01 { /** * 滑动窗口 * @param arr * @param w 窗口大小 * @return */ public static int[] slidingWindow(int[] arr, int w) { if (arr == null || arr.length < w || w < 1) { return null; } // 存放的是下标,头是最大值,尾是最小值。双端队列 LinkedList<Integer> indexList = new LinkedList<>(); // 窗口最大值的数组 int[] res = new int[arr.length - w + 1]; int index = 0; for (int i = 0; i < arr.length; i++) { // 当队列不为空时,peekLast拿到队列最小值(尾部)的下标,与当前i的值比较,小于弹出 while (!indexList.isEmpty() && arr[indexList.peekLast()] <= arr[i]) { indexList.pollLast(); } indexList.addLast(i); // 当前最大值下标被窗口滑过时,弹出 if (indexList.peekFirst() == i - w) { indexList.pollFirst(); } // 注意是peekFirst if (i >= w - 1) { res[index++] = arr[indexList.peekFirst()]; } } return res; } /** * 单调栈——无重复值 * 获得最近小于的,栈底到栈顶是从小到大 */ public static int[][] getNearLessNoRepeat(int[] arr) { // 栈中放的是数组的下标 Stack<Integer> stack = new Stack<>(); // [][0]表示左边最近小于的下标,[][1]表示右边最近最小的下标 int[][] res = new int[arr.length][2]; for (int i = 0; i < arr.length; i++) { while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) { int popIndex = stack.pop(); // 当前下标的左边最近小于的是当前下标弹出后的栈顶 int leftIndex = stack.isEmpty() ? -1 : stack.peek(); res[popIndex][0] = leftIndex; res[popIndex][1] = i; } stack.push(i); } while (!stack.isEmpty()) { int popIndex = stack.pop(); int leftIndex = stack.isEmpty() ? -1 : stack.peek(); res[popIndex][0] = leftIndex; res[popIndex][1] = -1; } return res; } /** * 单调栈——有重复值,使用队列存储重复值下标 * 获得最近小于的,栈底到栈顶是从小到大 * @param arr * @return */ public static int[][] getNearLess(int[] arr) { int[][] res = new int[arr.length][2]; Stack<ArrayList<Integer>> stack = new Stack<>(); for (int i = 0; i < arr.length; i++) { while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) { ArrayList<Integer> popIndexs = stack.pop(); // 最近的是队列中最后一个 int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer index : popIndexs) { res[index][0] = leftIndex; res[index][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()) { ArrayList<Integer> popIndexs = stack.pop(); // 最近的是队列中最后一个 int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1); for (Integer index : popIndexs) { res[index][0] = leftIndex; res[index][1] = -1; } } return res; } /** * 数组中累积和与最小值的乘积,假设叫做指标A * 给定一个数组,请返回子数组中,指标A最大的值。 * 以i为最小值的子数组的范围就是左边小于i的下标的右一个,右边小于i的下标的左一个。 * @param arr * @return */ public static int maxA(int[] arr) { int[][] nearLess = getNearLess(arr); int max = Integer.MIN_VALUE; for (int i = 0; i < arr.length; i++) { int sum = 0; int leftIndex = nearLess[i][0]; int rightIndex = nearLess[i][1]; if (rightIndex == -1) { rightIndex = arr.length; } while (leftIndex < rightIndex - 1) { sum = sum + arr[++leftIndex]; } max = Math.max(max, sum * arr[i]); } return max; } public static void main(String[] args) { // 滑动窗口 int[] arr = { 4, 3, 5, 4, 3, 3, 6, 7 }; int w = 3; System.out.println(Arrays.toString(slidingWindow(arr, w))); // 单调栈——无重复值 int[] arr1 = { 4, 3, 5, 6, 7 }; int[][] nearLessNoRepeat = getNearLessNoRepeat(arr1); System.out.println(Arrays.deepToString(nearLessNoRepeat)); // 单调栈——有重复值 int[] arr2 = { 4, 3, 5, 4, 3, 3, 6, 7 }; int[][] nearLess = getNearLess(arr2); System.out.println(Arrays.deepToString(nearLess)); // 单调栈的应用 int[] arr3 = { 4, 3, 5, 4, 3, 3, 6, 7 }; int i = maxA(arr3); System.out.println(i); } }
这篇关于算法基础提升——滑动窗口、单调栈和单调栈的应用的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-01后台管理开发学习:新手入门指南
- 2024-11-01后台管理系统开发学习:新手入门教程
- 2024-11-01后台开发学习:从入门到实践的简单教程
- 2024-11-01后台综合解决方案学习:从入门到初级实战教程
- 2024-11-01接口模块封装学习入门教程
- 2024-11-01请求动作封装学习:新手入门教程
- 2024-11-01登录鉴权入门:新手必读指南
- 2024-11-01动态面包屑入门:轻松掌握导航设计技巧
- 2024-11-01动态权限入门:新手必读指南
- 2024-11-01动态主题处理入门:新手必读指南