算法-16单调栈结构
2022/4/15 22:12:52
本文主要是介绍算法-16单调栈结构,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
单调栈(monotone-stack)是指栈内元素(栈底到栈顶)都是(严格)单调递增或者单调递减的。
如果有新的元素入栈,栈调整过程中 会将所有破坏单调性的栈顶元素出栈,并且出栈的元素不会再次入栈 。由于每个元素只有一次入栈和出栈的操作,所以 单调栈的维护时间复杂度是O(n) 。
单调栈性质:
- 单调栈里的元素具有单调性。
- 递增(减)栈中可以找到元素左右两侧比自身小(大)的第一个元素。
我们主要使用第二条性质,该性质主要体现在栈调整过程中,下面以自栈底到栈顶递增为例(假设所有元素都是唯一),当新元素入栈。
- 对于出栈元素来说:找到右侧第一个比自身小的元素。
- 对于新元素来说:等待所有破坏递增顺序的元素出栈后,找到左侧第一个比自身小的元素。
问题描述:给定不含重复值的数组arr,找到每个i位置左边和右边距离i最近的且值比i小的位置(没有返回-1),返回所有的位置信息。
输入描述:
第一行输入一个数字 n,表示数组 arr 的长度。以下一行输出 n个数字,表示数组的值。
输出描述:
输出n行,每行两个数字 L 和 R,如果不存在,则值为-1,下标从0开始。示例1
输入: 7 3 4 1 5 6 2 7 输出: -1 2 0 2 -1 -1 2 5 3 5 2 -1 5 -1
思路
常规实现:时间复杂度O(n^2)实现简单,每个位置向左和向右遍历一遍。
import java.util.Scanner; import java.util.Stack; public class Main{ public static int[][] rightWay(int[] arr) { int[][] res = new int[arr.length][2]; for(int i=0;i<arr.length;i++) { int leftLessIndex = -1; int rightLessIndex = -1; int cur = i - 1; while(cur >=0){ if(arr[cur]<arr[i]) { leftLessIndex = cur; break; } cur--; } cur = i + 1; while(cur < arr.length) { if(arr[cur] < arr[i]){ rightLessIndex = cur; break; } cur++; } res[i][0] = leftLessIndex; res[i][1] = rightLessIndex; } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int[] data = new int[n]; for(int i=0;i<data.length;i++) { data[i] = sc.nextInt(); } //int[][] result = getNearLessNoRepeat(data); int[][] result = rightWay(data); StringBuilder sb = new StringBuilder(); for(int i=0;i<result.length;i++) { sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n'); } System.out.print(sb); } } }
单调栈实现:寻找两边距离arr[i]最近且arr[i]小的索引,保持栈顶到栈底单调递减(寻找比arr[i]大的值,单调递增),栈中存放索引值。
import java.util.Scanner; import java.util.Stack; public class Main{ public static int[][] getNearLessNoRepeat(int[] arr) { int[][] res = new int[arr.length][2]; Stack<Integer> stack = new Stack<Integer>(); for(int i=0;i<arr.length;i++){ // 如果当前遍历到的数组的值小,需要弹出 while(!stack.isEmpty() && arr[stack.peek()]>arr[i]) { int popIndex = stack.pop(); int leftLessIndex = stack.isEmpty()?-1:stack.peek(); res[popIndex][0] = leftLessIndex; res[popIndex][1] = i; } stack.push(i); } while(!stack.isEmpty()) { int popIndex = stack.pop(); int leftLessIndex = stack.isEmpty()?-1:stack.peek(); res[popIndex][0] = leftLessIndex; res[popIndex][1] = -1; } return res; } public static void main(String[] args) { Scanner sc = new Scanner(System.in); while(sc.hasNext()){ int n = sc.nextInt(); int[] data = new int[n]; for(int i=0;i<data.length;i++) { data[i] = sc.nextInt(); } int[][] result = getNearLessNoRepeat(data); StringBuilder sb = new StringBuilder(); for(int i=0;i<result.length;i++) { sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n'); } System.out.print(sb); } } }
单调栈实现进阶问题:区别在于重复索引值用集合进行连接,栈中存放的是一个ArrayList。注意两点:
- arr[i]左边应该是上一个位置最晚加入的那个(如果有多个元素)
- 相等的情况直接在尾部加入,获取值的时候循环的获取该集合中的所有值(集合中元素值相等,索引值不同)
import java.util.List; import java.util.ArrayList; import java.util.Scanner; import java.util.Stack; public class Main{ public static int[][] getNearLess(int[] arr) { int[][] res = new int[arr.length][2]; Stack <List<Integer>> stack = new Stack <List<Integer>>(); for(int i=0;i<arr.length;i++) { while(!stack.isEmpty() && arr[stack.peek().get(0)]>arr[i]){ List<Integer> popIs = stack.pop(); int leftLessIndex = stack.isEmpty() ? -1:stack.peek().get(stack.peek().size()-1); for(Integer popi:popIs) { res[popi][0] = leftLessIndex; res[popi][1] = i; } } if(!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) { stack.peek().add(Integer.valueOf(i)); } else { ArrayList<Integer> list = new ArrayList<Integer>(); list.add(i); stack.push(list); } } while(!stack.isEmpty()) { List<Integer> popIs = stack.pop(); int leftLessIndex = stack.isEmpty()? -1:stack.peek().get(stack.peek().size() -1); for(Integer popi:popIs) { res[popi][0] = leftLessIndex; res[popi][1] = -1; } } return res; } public static void main(String args[]){ Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int[] data = new int[n]; for(int i=0;i<data.length;i++) { data[i] = sc.nextInt(); } int[][] result = getNearLess(data); StringBuilder sb = new StringBuilder(); for(int i=0;i<result.length;i++) { sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n'); } System.out.print(sb); } }
参考:https://www.jianshu.com/p/3c33d7087dfb
这篇关于算法-16单调栈结构的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 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动态主题处理入门:新手必读指南