155. 最小栈 & 20. 有效的括号
amp 有效 20 最小 括号 155
2023-06-13 09:11:16 时间
155. 最小栈
力扣题目链接[1]
设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack()
初始化堆栈对象。void push(int val)
将元素val推入堆栈。void pop()
删除堆栈顶部的元素。int top()
获取堆栈顶部的元素。int getMin()
获取堆栈中的最小元素。
提示:
-2^31 <= val <= 2^31 - 1
pop
、top
和getMin
操作总是在 「非空栈」 上调用push
,pop
,top
, andgetMin
最多被调用3 * 10^4
次
思路:
既可以使用辅助栈来维护一个最小值是栈顶的栈,也可以维护一个变量来实时保存最小值。这里采用第二种方式。
当执行入栈操作时,将val和原本的最小值进行比较,较小值便是最新的最小值。当执行出栈操作时,依旧需要实时更新最小值,方法是将栈里剩余的元素展开,比较出最小值。
通过实时维护最小值,便可以在常数时间内获取到当前栈的最小值。
实时替换
var MinStack = function() {
this.stack = [];
this.min = Number.MAX_SAFE_INTEGER;
};
/**
* @param {number} val
* @return {void}
*/
MinStack.prototype.push = function(val) {
this.stack.push(val);
this.min = Math.min(val, this.min);
};
/**
* @return {void}
*/
MinStack.prototype.pop = function() {
let val = this.stack.pop();
this.min = Math.min(...this.stack)
return val;
};
/**
* @return {number}
*/
MinStack.prototype.top = function() {
let length = this.stack.length;
if (!length) return null;
return this.stack[length - 1];
};
/**
* @return {number}
*/
MinStack.prototype.getMin = function() {
return this.min;
};
/**
* Your MinStack object will be instantiated and called as such:
* var obj = new MinStack()
* obj.push(val)
* obj.pop()
* var param_3 = obj.top()
* var param_4 = obj.getMin()
*/
20. 有效的括号
力扣题目链接[2]
给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。
有效字符串需满足:
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
「示例 1:」
输入:s = "()[]{}"
输出:true
「示例 2:」
输入:s = "([)]"
输出:false
「提示:」
1 <= s.length <= 104
s
仅由括号'()[]{}'
组成
思路:
本题是经典的栈应用问题。可以借助栈「后进先出」的特点求解。
维护一个栈用来存放尚未配对的括号。然后依次遍历字符串,如果栈顶元素与当前字符是配对的括号,就将栈顶元素跳出;如果不配对,则将当前字符放入栈顶。
如果最终所有字符括号都配对,栈肯定是空的。如果不配对,则栈不为空。因此判断栈是否为空,就可知晓是否括号配对。
栈
/**
* @param {string} s
* @return {boolean}
*/
var isValid = function(s) {
let stack = [];
let map = {
')': '(',
']': '[',
'}': '{',
};
let length = s.length;
let idx = 0;
while(idx < length) {
let stackLen = stack.length;
if (!stackLen) {
stack.push(s[idx++]);
continue;
}
stack[stackLen - 1] === map[s[idx]] ? stack.pop() : stack.push(s[idx]);
idx++;
}
return !stack.length;
};
总结
今天的两道题均考察了栈的应用,难度系数简单。需要牢记栈的特点是后进先出。比较常见的应用是借用辅助栈来维护极值,是典型的使用空间换时间的做法,方便在常数时间内获取到极值。
参考资料
[1]
力扣题目链接: https://leetcode-cn.com/problems/min-stack/
[2]
力扣题目链接: https://leetcode-cn.com/problems/valid-parentheses/
相关文章
- Java Web Servlet (Part D)- File Upload & Download
- Spring学习笔记(三十)——SpringBoot对象拷贝总结&Mapstruct
- python copy&deepcopy
- App Cleaner & Uninstaller 应用程序卸载清理工具,彻底清除残留文件垃圾!
- 免杀&&抽奖|python进行shellcode免杀
- 国科大&港中文提出带视觉语言验证和迭代推理的Visual Grounding框架,性能SOTA,代码已开源!(CVPR2022)
- ChunJun&OceanBase联合方案首次发布:构建一体化数据集成方案
- [- Flutter 数据&状态篇 -] setState
- 通过nginx日志统计一段时间内ip的访问次数进行排序&访问量统计
- V&NCTF2021_MISC官方wp
- Dapr 与 NestJs ,实战编写一个 Pub & Sub 装饰器
- 7 Papers & Radios | Hinton前向-前向神经网络训练算法;科学家造出「虫洞」登Nature封面
- 腾讯云HiFlow场景连接器 联动对象存储&企业网盘,打通数据分发“最后一公里”
- Easyensemble&LightGBM-应对气象样本不平衡问题的有效算法(支持各类基模型接入与新增优化参数)
- BBS(php&mysql)完整版(二)
- C++中dynamic_cast<>的使用方法小结