算法通关村第4关【白银】| 栈的经典算法问题

news/2024/12/22 20:16:06/

1.括号匹配问题

思路:将左括号压入栈中,遍历字符串,当遇到右括号就出栈,判断是否是匹配的一对,不是就返回false(因为按照顺序所以当遇到右括号出栈一定要是匹配的)。使用Map来简化ifelse 

class Solution {public boolean isValid(String s) {int len = s.length();if(len%2 != 0){return false;}Map<Character,Character> map = new HashMap<>();map.put('(',')');map.put('[',']');map.put('{','}');Deque<Character> stack = new LinkedList<>();for(int i = 0;i<len;i++){char c = s.charAt(i);if(map.containsKey(c)){stack.push(c);}else{if(stack.isEmpty() || c != map.get(stack.pop())){return false;}}}return stack.isEmpty();}
}

 2.最小栈

 

关键是使用辅助栈,并且同步存取,存的是最新的最小值,如果最小值被弹出栈了,因为同步的原因辅助栈中的最小值也将会消失。

class MinStack {Deque<Integer> min;Deque<Integer> stack;public MinStack() {stack = new LinkedList<>();min = new LinkedList<>();min.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);min.push(Math.min(val,min.peek()));}public void pop() {stack.pop();min.pop();}public int top() {return stack.peek();}public int getMin() {return min.peek();}
}

3.最大栈

设计一个最大栈数据结构,支持查找最大元素

与最小栈一样,不同的是需要实现popMax()将栈中最大元素弹出,此处使用额外辅助栈,将原栈中元素弹出放入辅助栈中,待最大的元素找出弹出后,再倒回去。注意的时两个栈同时存取

class MaxStack {Stack<Integer> stack;Stack<Integer> maxStack;public MaxStack() {stack = new Stack();maxStack = new Stack();}public void push(int x) {int max = maxStack.isEmpty() ? x : maxStack.peek();maxStack.push(max > x ? max : x);stack.push(x);}public int pop() {maxStack.pop();return stack.pop();}public int top() {return stack.peek();}public int peekMax() {return maxStack.peek();}public int popMax() {int max = peekMax();Stack<Integer> buffer = new Stack();while (top() != max) buffer.push(pop());pop();while (!buffer.isEmpty()) push(buffer.pop());return max;}public static void main(String[] args) {MaxStack stack = new MaxStack();stack.push(2);stack.push(5);stack.push(1);System.out.println(stack.top());System.out.println(stack.popMax());System.out.println(stack.peekMax());}
}


http://www.ppmy.cn/news/1041993.html

相关文章

《Java极简设计模式》第04章:建造者模式(Builder)

作者&#xff1a;冰河 星球&#xff1a;http://m6z.cn/6aeFbs 博客&#xff1a;https://binghe.gitcode.host 文章汇总&#xff1a;https://binghe.gitcode.host/md/all/all.html 源码地址&#xff1a;https://github.com/binghe001/java-simple-design-patterns/tree/master/j…

Typora上传文件到Gitee

工作内容,不对外开放 一、Typora上传笔记到CSDN 一、安装node.js 官网链接:Node.js (nodejs.org) 下载后得到一个.msi文件,双击即可。 win + R 打开CMD,基于node -v 和npm -v,验证是否安装成功: 二、配置Gitee 1、新建仓库 2、开源此仓库 2.1、初始化readme文件

前端---需要了解浏览器相关知识--浏览器请求服务器资源---缓存

知识点1: 掘金1&#xff1a;浏览器缓存 掘金2 :浏览器缓存 一、浏览器缓存 请求&#xff08;静态资源 &#xff5c; 动态资源&#xff09; 一、缓存是什么&#xff1f; 如果没有缓存的机制 每次都要重新请求静态资源 1.从网络上的下载时间&#xff0c;肯定大于从硬盘里读的…

【探索Linux】—— 强大的命令行工具 P.5(yum工具、git 命令行提交代码)

阅读导航 前言一、软件包管理器 yum1.yum的概念yum的基本指令使用例子 二、git 命令行提交代码总结温馨提示 前言 前面我们讲了C语言的基础知识&#xff0c;也了解了一些数据结构&#xff0c;并且讲了有关C的一些知识&#xff0c;也学习了一些Linux的基本操作&#xff0c;也了…

R语言APSIM模型进阶应用与参数优化、批量模拟实践技术

随着数字农业和智慧农业的发展&#xff0c;基于过程的农业生产系统模型在模拟作物对气候变化的响应与适应、农田管理优化、作物品种和株型筛选、农田固碳和温室气体排放等领域扮演着越来越重要的作用。APSIM (Agricultural Production Systems sIMulator)模型是世界知名的作物生…

【golang】函数(func)正确使用姿势

函数不但可以用于封装代码、分割功能、解耦逻辑&#xff0c;还可以化身为普通的值&#xff0c;在其他函数间传递、赋予变量、做类型判断和转换等等&#xff0c;就像切片和字典的值那样。 而更深层次的含义就是&#xff1a;函数值可以由此成为能够被随意传播的独立逻辑组件&…

Springboot+vue网上招聘系统

系统的首页&#xff0c;头部有三个选项框&#xff0c;第一个是主页&#xff0c;第二个是才艺技能平台&#xff0c;第三个是登录注册。1.1.2 登录注册模块 系统的登录注册包括登录和注册两个部分。所有系统用户使用后台管理功能都需要经行登录&#xff0c;根据选择不同的身份进入…

Springboot 整合MQ实现延时队列入门

延时队列 添加依赖配置文件队列TTL代码架构图交换机、队列、绑定配置文件代码生产者代码消费者代码延时队列优化添加普通队列配置代码生产者发送消息是进行设置消息的ttl 通过MQ 插件实现延时队列代码架构图配置交换机生产者代码消费者代码测试发送 添加依赖 <!-- rabbitMQ …