算法通过村第四关-栈白银笔记|括号问题
文章目录
- 前言
- 1. 括号匹配问题
- 2. 最小栈问题
- 3. 最大栈
- 总结
前言
提示:如果让我送给年轻人四个字,就是:量力而行。 量力而行不会失眠,不会啃老,不会为各种考试焦虑。顺其自然活得轻松。其实,量力而行最易大展宏图。
栈在常见的数据结构中也是比较常用的,一些经典的题目对于理解栈很有帮助,就那他们练手吧
1. 括号匹配问题
栈的典型题目,栈常用在括号匹配,表达式计算等等,我看就来看看这个最经典的问题:
参考题目介绍:20. 有效的括号 - 力扣(LeetCode)


对于这个题目来说,还是比较简单的,要处理的问题难题时判断符号是否一组,我们可以先用Hash将所有的符合存储下来,左半边就做key,右半边做value。遍历字符串的时候,遇到左半边符号就入栈,遇到右半边的符号就与栈顶的符号进行比较,不匹配就返回false;
public static boolean isValid(String s) {if (s.length() < 2) {return false;}HashMap<Character, Character> map = new HashMap<Character, Character>();map.put('[', ']');map.put('(', ')');map.put('{', '}');Stack<Character> stack = new Stack<>();for (int i = 0; i < s.length(); i++) {char c = s.charAt(i);if (map.containsKey(c)) {stack.push(c);} else {if (!stack.isEmpty()) {// 拿到栈顶的左括号Character left = stack.pop();Character right = map.get(left);if (right != c) {return false;}} else {return false;}}}return stack.isEmpty();}
当然类似的题目还有很多,有难有易,可以多杀杀,挫挫锐气哈哈哈🤣,这里我就不一一举例🌰了
2. 最小栈问题
参考题目介绍:155. 最小栈 - 力扣(LeetCode)


不知到你会不会和我一样题目还没理解什么意思的,别慌,那我们就来看看,这个题要怎么解。我觉得本题的关键在于getMin()到底表示什么,我们可以画一个图;

我们看到这个图,大致已经有了思路,Min栈内,中间-2元素,对它的理解就是解题的关键。
题目要求在常数时间内获取到栈中的最小值,也就是我们不能在getMin()的时候去计算,而是直接返回值,也就说只能在push和pop中做一些操作了。
栈的特性时先进后出,这个很重要,我们可以这么做,我们将元素(a)存入栈中的时候,就把当前的最小值(m)记录下来,也就是说如果a时栈顶,最小是就是m,我们可以直接返回。
这样的话我们就可以设计一个数据结构,使得每个元素a与其相应的最小值m时刻保持一致,所以我们需要一个辅助栈,与元素栈插入和删除保持一致,用来存储每个元素对应的最小值。
- 当元素要入栈的时候,我们取当前辅助栈的栈顶元素与之比较,该元素小,就将这个值存入辅助栈中;
- 当一个元素要出栈时,我们把辅助栈的栈顶元素一并出栈
这样的话,在任意时刻,栈内元素的最小值就存储在辅助栈的栈顶元素中。
这样的话代码写起来就非常简单了🤣
class MinStack {private static Stack<Integer> xStack;private static Stack<Integer> minStack;public MinStack() {xStack = new Stack<>();minStack = new Stack<>();// 占位符minStack.push(Integer.MAX_VALUE);}public void push(int val) {xStack.push(val);minStack.push(Math.min(val,minStack.peek()));}public void pop() {xStack.pop();minStack.pop();}public int top() {return xStack.peek();}public int getMin() {return minStack.peek();}
}/*** Your MinStack object will be instantiated and called as such:* MinStack obj = new MinStack();* obj.push(val);* obj.pop();* int param_3 = obj.top();* int param_4 = obj.getMin();*/
有最小栈那会不会有最大栈呢?哈哈哈,他来了
3. 最大栈
参考题目介绍:716. 最大栈 - 力扣(LeetCode)
设计一个最大栈数据结构,及支持栈操作,有支持查找栈中最大元素。

这个题和上一题相反,处理方法上一致,一个普通的栈可以支持前三种操作,push(x),pop()和top(),这里我们需要考虑的是后面的操作peekMax()和popMax()。
对于peekMax(),我们可以用另一个栈来存储每个位置对应的最大值,比如第一个栈的元素为[2,1,5,3,9],那么第二个栈的元素就是[2,2,5,5,9]。在push(x)操作时,只需要将第二个栈顶元素和x的最大值入栈就行,而pop()操作只需要将第二个栈进行出栈。
对于popMax(),由于我们指导当前栈中最大元素值,我们就可以将两个栈同时出栈,并存储第一个栈出栈的所有值。当某个时刻第一个栈中的出栈元素等于当前栈中的最大值时,我们就找到了最大元素。此时我们将之前的第一个栈的所有元素重新入栈,并同步更新到第二栈中,就完成了popMax()操作;
代码展示如下:
import java.util.Stack;class MaxStack {public static Stack<Integer> xStack;public static Stack<Integer> maxStack;public MaxStack() {xStack = new Stack<Integer>();maxStack = new Stack<Integer>();}public void push(int val) {xStack.push(val);int max = maxStack.isEmpty() ? val : maxStack.peek();maxStack.push(max > val ? max : val);}public int pop() {maxStack.pop();return xStack.pop();}public int top() {return xStack.peek();}public int peekMax() {return maxStack.peek();}public int popMax() {int max = peekMax();Stack<Integer> stack = new Stack<Integer>();while(top() != max){stack.push(pop());}pop();while(!stack.isEmpty()){push(stack.pop());}return max;}}
总结
提示:栈的操作有时需要一个辅助栈,来帮助解决问题。
相关文章:
算法通过村第四关-栈白银笔记|括号问题
文章目录 前言1. 括号匹配问题2. 最小栈问题3. 最大栈 总结 前言 提示:如果让我送给年轻人四个字,就是:量力而行。 量力而行不会失眠,不会啃老,不会为各种考试焦虑。顺其自然活得轻松。其实,量力而行最易大…...
基于MATLAB开发AUTOSAR软件应用层Code mapping专题-part 6 Data Transfers标签页介绍
这篇文章我们介绍下Data Transfers页的配置,这里边包含的内容是IRV,我之前的文章里有讲解过IRV就是 Inter-Runnable Variables,内部runnable的之间传递数据的变量,在讲解Data Store memory的文章里我们提到了,irv也可以使用Data Store memory的方式来实现,我们先看下IRV如何…...
HDLBits-Verilog学习记录 | Verilog Language-Vectors
文章目录 11.vectors | vector012.vectors in more detail | vector113.Vector part select | Vector214.Bitwise operators | Vectorgates15.Four-input gates | Gates416.Vector concatenation operator | Vector317.Vector reversal 1 | Vectorr18. Replication operator | …...
彻底搞懂 PHP 运算符 ?: 和 ??
文章目录 快速掌握?: 短三元运算符?? NULL 合并运算符 附上官方文档查阅方式 快速掌握 ?: 短三元运算符 ?: 称之为短三元运算符,它是我们熟悉的三元运算符(也叫做条件运算符)的一种特殊写法,也就是省略了三元运算符中间的部…...
贝叶斯人工智能大脑与 ChatGPT
文章目录 一、前言二、主要内容 🍉 CSDN 叶庭云:https://yetingyun.blog.csdn.net/ 一、前言 论文地址:https://arxiv.org/abs/2308.14732 这篇论文旨在研究 Chat Generative Pre-trained Transformer(ChatGPT)在贝叶斯…...
适应高速率网络设备的-2.5G/5G/10G网络变压器/网络滤波器介绍
Hqst盈盛(华强盛)电子导读:在高速发展的互联网/物联网时代,为满足高网速的网络数据传输需求,网络设备在制造中也要选用合适的网络变压器/滤波器产品,有哪些可供选择的高速率网络变压器产品也是广大采购人员…...
「Redis」1. 数据类型的底层实现
前言:在这篇博文中,我们将简单总结在面试中怎么回答Redis数据类型的底层实现。 因为面试时间就那么点,言简意赅的描述自己会的知识显得尤为重要‼️ 文章目录 0.1. String 的底层实现原理0.2. 列表的底层实现原理0.3. 字典的底层实现原理0.4.…...
Win11共享文件,能发现主机但无法访问,提示找不到网络路径
加密长度选择如下: 参考以下链接: Redirectinghttps://answers.microsoft.com/zh-hans/windows/forum/all/win11%E8%AE%BE%E7%BD%AE%E6%96%87%E4%BB%B6%E5%A4%B9/554343a9-d963-449a-aa59-ce1e6f7c8982?tabAllReplies#tabs...
ROS中使用Navigation报错信息
在ROS中使用遇到了几个Navigation报错信息,在这里进行下记录: [ WARN] [1688134727.429227824]: The origin for the sensor at (7.35, 13.12) is out of map bounds. So, the costmap cannot raytrace for it. 解决办法: [ WARN] [16881…...
three.js(六):自适应设备分辨率
自适应设备分辨率 当今大多数的PC端和移动端显示器都是HD-DPI显示器。HD-DPI 是High Definition-Dots Per Inch 的简称,意思是高分辨率显示器。不同设备的显示器的分辨率是不一样的。 以上图中的iPhone6/7/8 为例:375*667 代表的手机的屏幕的物理尺寸&a…...
Kubernetes对象深入学习之五:TypeMeta无效之谜
欢迎访问我的GitHub 这里分类和汇总了欣宸的全部原创(含配套源码):https://github.com/zq2599/blog_demos 本篇概览 本文是《Kubernetes对象深入学习之五》系列的第五篇,从前文的分析也能看出,代表对象类型的schema.ObjectKind,于…...
Gitlab设置中文
1. 打开设置 2.选择首选项Preferences 3. 下滑选择本地化选项Localization,设置简体中文,然后保存更改save changes。刷新网页即可。...
【微服务部署】05-安全:强制HTTPS
文章目录 安全 : 强制HTTPS的两种方式1. Ingress配置重定向2. 应用程序配置3. Ingress配置4. 应用程序配置代码总结 安全 : 强制HTTPS的两种方式 互联网发展中,安全是非常重要的,由其是现在HTTPS非常普及的情况下,应用程序在公网上一般都会被…...
Config:服务端连接Git配置
创建子模块 Pom文件 <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"http://maven.apache.org…...
c++学习 之 类和对象 public , protected ,private
前言 在C中,访问控制修饰符(Access Control Modifiers)用于控制类的成员(成员变量和成员函数)的访问权限。这些修饰符分为三种:public、protected和private。它们定义了成员可以在何处访问,具体…...
ECharts图表动态修改series显示隐藏
文章目录 1、前言2、思路3、实现 1、前言 最近做的大数据平台,里面很多部分用到了ECharts,其中有个功能,要求将图表分组,根据用户选择的组,来确定ECharts要显示那些线条和柱子,也就是动态的显示option.seri…...
云服务器(Centos7系统)配置JAVA+mysql+tomcat 环境
文章主要内容来源云服务器(Centos7系统)部署javaweb项目(二)配置JAVAmysqltomcat 环境_man_zuo的博客-CSDN博客 模仿途中遇到的问题 连接无效 有时连接无法下载,可能是过期了,将其更换为官网给的下载连接即…...
【计算机视觉 | 目标检测】目标检测常用数据集及其介绍(四)
文章目录 一、JTA (Joint Track Auto)二、AVD (Active Vision Dataset)三、ExDark (Exclusively Dark Image Dataset)四、InteriorNet五、ScanRefer Dataset六、FlickrLogos-32七、SIXray八、Clear Weather (DENSE)九、DVQA (Data Visualizations via Question Answering)十、M…...
Dockerfile制作镜像与搭建LAMP环境
一.编写Dockerfile制作Web应用系统nginx镜像,生成镜像nginx:v1.1,并推送其到私有仓库。具体要求如下: (1)基于centos基础镜像; (2)指定作者信息; (3ÿ…...
Linux系统中查看端口的方法
一、使用netstat命令 netstat命令是一种非常实用的命令,可以用来显示网络连接、路由表、网络接口和网络统计信息等。它还可以用来显示系统中正在监听的端口。要查看端口,只需在终端中输入以下命令: netstat -tuln 这个命令的意思是列出所有…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
《用户共鸣指数(E)驱动品牌大模型种草:如何抢占大模型搜索结果情感高地》
在注意力分散、内容高度同质化的时代,情感连接已成为品牌破圈的关键通道。我们在服务大量品牌客户的过程中发现,消费者对内容的“有感”程度,正日益成为影响品牌传播效率与转化率的核心变量。在生成式AI驱动的内容生成与推荐环境中࿰…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
(转)什么是DockerCompose?它有什么作用?
一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用,而无需手动一个个创建和运行容器。 Compose文件是一个文本文件,通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...
大学生职业发展与就业创业指导教学评价
这里是引用 作为软工2203/2204班的学生,我们非常感谢您在《大学生职业发展与就业创业指导》课程中的悉心教导。这门课程对我们即将面临实习和就业的工科学生来说至关重要,而您认真负责的教学态度,让课程的每一部分都充满了实用价值。 尤其让我…...
Web 架构之 CDN 加速原理与落地实践
文章目录 一、思维导图二、正文内容(一)CDN 基础概念1. 定义2. 组成部分 (二)CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 (三)CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 …...
AI,如何重构理解、匹配与决策?
AI 时代,我们如何理解消费? 作者|王彬 封面|Unplash 人们通过信息理解世界。 曾几何时,PC 与移动互联网重塑了人们的购物路径:信息变得唾手可得,商品决策变得高度依赖内容。 但 AI 时代的来…...
CVE-2020-17519源码分析与漏洞复现(Flink 任意文件读取)
漏洞概览 漏洞名称:Apache Flink REST API 任意文件读取漏洞CVE编号:CVE-2020-17519CVSS评分:7.5影响版本:Apache Flink 1.11.0、1.11.1、1.11.2修复版本:≥ 1.11.3 或 ≥ 1.12.0漏洞类型:路径遍历&#x…...
C/C++ 中附加包含目录、附加库目录与附加依赖项详解
在 C/C 编程的编译和链接过程中,附加包含目录、附加库目录和附加依赖项是三个至关重要的设置,它们相互配合,确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中,这些概念容易让人混淆,但深入理解它们的作用和联…...
push [特殊字符] present
push 🆚 present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中,push 和 present 是两种不同的视图控制器切换方式,它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...
