java实现单调栈和单调队列
2021/11/24 20:12:54
本文主要是介绍java实现单调栈和单调队列,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
package com.test.autimatic; import org.apache.poi.ss.formula.functions.T; import java.util.*; /** * @author 25338 * @version 1.0 * @date 2021/11/24 17:04 * @description */ public class SingleQueueAndSingleStack { public static void main(String[] args) { //mystack--获取比当前值大的最近的元素 int[] arr = {2,1,3,4,3}; List<Integer> list = new ArrayList<>();//最终数据 MyStack<Integer> myStack = new MyStack<>(); for (int i = arr.length-1; i >= 0; i--) { Integer add = myStack.add(arr[i]); list.add(add==null?-1:add); } System.out.println(list); System.out.println("---------------------------"); //myqueue---单调队列,获取一为3的长度段区间内的最大值 int[] arrQue = {2,1,3,4,3}; MyQueue<Integer> queue = new MyQueue<>(); List<Integer> endMax = new ArrayList<>(); for (int i = 0; i < arrQue.length; i++) { queue.add(arrQue[i]); if(i > 2) { queue.delete(arrQue[i-3]); } endMax.add(queue.max()); } System.out.println(endMax); } /** * 单调栈--递增 */ public static class MyStack<Key extends Comparable<Key>>{ private Stack<Key> stack;//存储数据的队列 private Key max;//存储最大元素 /** * 构造函数初始化集合 */ public MyStack() { this.stack = new Stack<>(); } /** * 添加数据---主要(--)外加输出比当前值大的数据 * @param key */ public Key add(Key key){ //如果stack不为空且栈顶元素比目标值小,删除栈顶元素-维持低增粘 while (!stack.isEmpty() && stack.peek().compareTo(key) < 0){ stack.pop(); } //设置最大值 if(stack.isEmpty()){ max = key; } //获取倒数第二个数 Key end = stack.isEmpty()? null:stack.peek(); //添加元素 stack.push(key); return end; } /** * 删除最小元素---一般用不到 * @return */ public Key del(){ if(!stack.isEmpty()){ return stack.pop(); }else{ max = null; } return null; } /** * 获取最大值 --- 一般用不到 * @return */ public Key max(){ return this.max; } } /** * 单调队列---递增 */ public static class MyQueue<key extends Comparable<key>>{ //数据集合--- private Deque<key> queue; public MyQueue() { this.queue = new LinkedList<>(); } /** * 添加元素 * @param key */ public void add(key key){ //先进先出--从头进去数据 while (!queue.isEmpty() && queue.peekFirst().compareTo(key) < 0 ){ queue.pollFirst();//如果比队头大,则删去队头元素 } //添加元素 queue.addFirst(key); } /** * 末尾元素即为最大值 * @return */ public key max(){ if(queue.isEmpty()){ return null; } //返回最后一个元素就是最大值 return queue.peekLast(); } /** * 删除元素 * @param key * @return */ public key delete(key key){ if(!queue.isEmpty() && queue.peekLast().compareTo(key) == 0){ return queue.pollLast();//如果最后一个数据为当前要删除的数据则删除 }else{ return null; } } } }
这篇关于java实现单调栈和单调队列的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-11-02Java管理系统项目实战入门教程
- 2024-11-02Java监控系统项目实战教程
- 2024-11-02Java就业项目项目实战:从入门到初级工程师的必备技能
- 2024-11-02Java全端项目实战入门教程
- 2024-11-02Java全栈项目实战:从入门到初级应用
- 2024-11-02Java日志系统项目实战:初学者完全指南
- 2024-11-02Java微服务系统项目实战入门教程
- 2024-11-02Java微服务项目实战:新手入门指南
- 2024-11-02Java项目实战:新手入门教程
- 2024-11-02Java小程序项目实战:从入门到简单应用