首页 > 其他分享 >leetcode:最小栈

leetcode:最小栈

时间:2023-04-17 12:40:35浏览次数:48  
标签:minStack 元素 栈顶 最小 pop 最小值 push leetcode

问题描述

设计一个支持 push ,pop ,top 操作,并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

MinStack() 初始化堆栈对象。 void push(int val) 将元素val推入堆栈。 void pop() 删除堆栈顶部的元素。 int top() 获取堆栈顶部的元素。 int getMin() 获取堆栈中的最小元素。  

示例 1:

输入:
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出:
[null,null,null,null,-3,null,0,-2]

解释:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示:

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

题目地址:155. 最小栈

解题思路

使用两个栈:

  • 一个栈存放全部的元素,push,pop都是正常操作这个正常栈。
  • 另一个存放最小栈。 每次push,如果比最小栈的栈顶还小,我们就push进最小栈,否则不操作
  • 每次pop的时候,我们都判断其是否和最小栈栈顶元素相同,如果相同,那么我们pop掉最小栈的栈顶元素即可

代码:

/**
 * initialize your data structure here.
 */
var MinStack = function() {
    this.stack = []
    this.minStack = []
};

/** 
 * @param {number} x
 * @return {void}
 */
MinStack.prototype.push = function(x) {
    this.stack.push(x)
    if (this.minStack.length == 0 ||  x <= this.minStack[this.minStack.length - 1]) {
        this.minStack.push(x)
    }
};

/**
 * @return {void}
 */
MinStack.prototype.pop = function() {
    const x = this.stack.pop()
    if (x !== void 0 &&  x === this.minStack[this.minStack.length - 1]) {
        this.minStack.pop()
    }
};

/**
 * @return {number}
 */
MinStack.prototype.top = function() {
    return this.stack[this.stack.length - 1]
};

/**
 * @return {number}
 */
MinStack.prototype.min = function() {
    return this.minStack[this.minStack.length - 1]
};

/** 
 * MinStack 对象 实例化并以这种方式调用
 * var obj = new MinStack()
 * obj.push(x)
 * obj.pop()
 * var param_3 = obj.top()
 * var param_4 = obj.min()
 */

这段代码实现了一个最小栈(Min Stack)数据结构,它支持以下操作:

push(x):将元素 x 压入栈中。 pop():弹出栈顶元素。 top():获取栈顶元素。 min():获取栈中的最小元素。 这个最小栈的实现使用了两个栈,一个是普通的栈 stack,另一个是最小值栈 minStack。在 push(x) 操作中,首先将元素 x 压入普通栈 stack 中,然后判断最小值栈 minStack 是否为空,或者 x 是否小于等于最小值栈的栈顶元素,如果是,则将 x 压入最小值栈 minStack 中。这样,最小值栈的栈顶元素始终是当前栈中的最小值。

在 pop() 操作中,首先弹出普通栈 stack 的栈顶元素 x,然后判断 x 是否等于最小值栈 minStack 的栈顶元素,如果是,则也将最小值栈的栈顶元素弹出。这样,最小值栈的栈顶元素仍然是当前栈中的最小值。

在 top() 操作中,直接返回普通栈 stack 的栈顶元素。

在 min() 操作中,直接返回最小值栈 minStack 的栈顶元素。

这个最小栈的实现可以保证在常数时间内完成所有操作,包括 push(x)、pop()、top() 和 min()。

总结: 往minstack中 push的判断条件。 应该是stack为空或者x小于等于minstack栈顶元素

标签:minStack,元素,栈顶,最小,pop,最小值,push,leetcode
From: https://blog.51cto.com/codeniu/6194935

相关文章

  • MATLAB 蚁群算法 配网重构 故障恢复 最小失电负荷 以提高供电可靠性和降低线损为目标,
    MATLAB蚁群算法配网重构故障恢复最小失电负荷以提高供电可靠性和降低线损为目标,建立配电网重构的优化模型,对算法进行综合比较,选取蚁群算法进行网络重构的优化。以IEEE33节点的配电网重构为算例,验证了本模型的可用性及利用蚁群算法解决重构算法的高效性。ID:4865067112444......
  • 基于最小二乘法和快速解耦法的电网状态估计
    基于最小二乘法和快速解耦法的电网状态估计测试环境:MATLAB电网状态估计问题的实质是当方程的个数大于变量的个数时,对方程变量进行无偏估计。对于电网系统,变量为节点电压(即状态值,由实部和虚部),节点和支路功率的一部分(包含由于客观条件造成的误差)是数量测量,即将被给予。方......
  • LeetCode Top100: 爬楼梯 (python)
     假设你正在爬楼梯。需要 n 阶你才能到达楼顶。每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢? 示例1:输入:n=2输出:2解释:有两种方法可以爬到楼顶。1.1阶+1阶2.2阶示例2:输入:n=3输出:3解释:有三种方法可以爬到楼顶。1.1阶+1......
  • leetcode160-相交链表
    leetcode160方法一:哈希表思路:先创建一个unordered_set,存放ListNode*类型的变量先遍历其中一个链表,把所有节点的指针放在set中再遍历另一个链表,查找是否存在一个节点已经在set中,如果存在则说明这是它们的相交节点的指针,返回这个指针,如果不存在则说明不存在相交节点,......
  • LeetCode-Top100: 有效的括号 (python)
     给定一个只包括 '(',')','{','}','[',']' 的字符串 s ,判断字符串是否有效。有效字符串需满足:左括号必须用相同类型的右括号闭合。左括号必须以正确的顺序闭合。每个右括号都有一个对应的相同类型的左括号。 示例1:输入:s="()"输出:true示例 2:输入:s="()[]{}"输......
  • LeetCode-Top100:两数之和(python)
     给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。你可以按任意顺序返回答案。 示例1:输入:nums=......
  • leetcode_打卡5
    leetcode_打卡5题目:345.反转字符串中的元音字母思路:双指针classSolution{publicStringreverseVowels(Strings){intn=s.length();char[]arr=s.toCharArray();inti=0;intj=n-1;while(i<j){while(i<n&&!yua......
  • P6134 [JSOI2015]最小表示
    P6134[JSOI2015]最小表示思:有向无环图,想到拓扑排序。逆序枚举,因为排序后下标小的点用到它前面的点的联通性。对其连接的点按照拓扑序由小到大进行排序(靠前的点可以连接的点多,那么可以删的边数也变多。其余套路与可达性统计类似,注意代码细节。#include<bits/stdc++.h>......
  • LeetCode 双周赛 102,模拟 / BFS / Dijkstra / Floyd
    本文已收录到AndroidFamily,技术和职场问题,请关注公众号[彭旭锐]提问。大家好,欢迎来到小彭的LeetCode周赛解题报告。昨晚是LeetCode双周赛第102场,你参加了吗?这场比赛比较简单,拼的是板子手速,继上周掉大分后算是回了一口血......
  • 最小生成树学习笔记
    定义最小生成树是指给定一个带权连通图G,如果里面有一个子图G'中的边权和加起来最小并且使得所有的点都能两两相通。性质从上述的定义可以看出,最小生成树有以下性质:如果图G中有n个点的话,G'中的边数为n-1且G'中不含有环。最小生成树可能是一个,也可能是多个。......