力扣题目链接[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
, and getMin
最多被调用 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()
*/
力扣题目链接[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/