java算法题解LeetCode30包含min函数的栈实例

目录
  • 题目
  • 解题思路

题目

剑指 Offer 30. 包含min函数的栈 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。

示例:

MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回 -3. minStack.pop(); minStack.top(); --> 返回 0. minStack.min(); --> 返回 -2.

提示： 各函数的调用总次数不超过 20000 次

解题思路

1.题目要求实现的最小返回其实不难，最简单的，只需要去排序就可以了，但是这样的话，无法保证调用 min、push 及 pop 的时间复杂度都是 O(1)

2.正常一个栈的push、pop、peek的时间复杂度都是 O(1)，那么现在就是想办法去解决，min函数时间复杂度的问题了？

3.既然题目限制了时间复杂度，那么这时我们可以想一下，是否可以借助空间来实现？使用辅助栈？

4.一个栈是主栈 stackstack，另一个是辅助栈 minStackminStack，用于存放对应主栈不同时期的最小值

import java.util.Stack;
class MinStack {
	Stack<Integer> stack;
	Stack<Integer> minstack;
	/** initialize your data structure here. */
	public MinStack() {
		stack = new Stack<Integer>();
		minstack = new Stack<Integer>();
	}
	public void push(int x) {
		stack.push(x);
		if (minstack.isEmpty()) {
			minstack.push(x);
		} else {
			int k = minstack.peek();
			if (k > x) {
				minstack.push(x);
			} else {
				minstack.push(k);
			}
		}
	}
	public void pop() {
		stack.pop();
		minstack.pop();
	}
	public int top() {
		return stack.peek();
	}
	public int min() {
		return minstack.peek();
	}
}
/**
 * Your MinStack object will be instantiated and called as such: MinStack obj =
 * new MinStack(); obj.push(x); obj.pop(); int param_3 = obj.top(); int param_4
 * = obj.min();
 */

以上就是java算法题解LeetCode30包含min函数的栈实例的详细内容，更多关于java算法包含min函数的栈的资料请关注我们其它相关文章！

赞 (0)

相关推荐

  • java算法题解LeetCode35复杂链表的复制实例

    目录 题目 示例 1: 示例 2: 示例 3: 示例 4: 解题思路 题目 AC 剑指 Offer 35. 复杂链表的复制请实现 copyRandomList 函数,复制一个复杂链表.在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null. 示例 1: 输入:head = [[7,null],[13,0],[11,4],[10,2],[1,0]] 输出:[[7,null],[13,0],[11,4],[10,2],[1,0]

  • Java C++题解leetcode816模糊坐标示例

    目录 题目 思路:枚举 Java C++ Rust 总结 题目 题目要求 思路:枚举 既然要输出每种可能了,那必然不能“偷懒”,就暴力枚举咯: 在每个间隔处添加逗号: 定义函数decPnt(sta, end)分别列举逗号左右两边的数能构成的可能性: 同样在每个间隔添加小数点: 注意两种不合法的结构——前导0和后缀0: 不要忘记无小数点的整数版本, 分别组合两边的不同可能性,根据要求各式加入答案. Java class Solution { String str; public List<Stri

  • Java C++题解leetcode 1684统计一致字符串的数目示例

    目录 题目 思路:模拟 Java C++ Rust 题目 题目要求 思路:模拟 用一个哈希表记录可出现的字母,然后逐一遍历每个单词每个字母,符合条件则结果加一. Java class Solution { public int countConsistentStrings(String allowed, String[] words) { boolean[] hash = new boolean[26]; for (var a : allowed.toCharArray()) hash[a -

  • Java C++刷题leetcode1106解析布尔表达式

    目录 题目 思路:栈[计算器] Java C++ Rust 总结 题目 题目要求 思路:栈[计算器] 和计算器原理类似,分别用两个栈存操作数和操作符,然后到)就开始运算前面的内容,括号里运算都相同所以还是比较简单的. 要注意字母t.f和布尔值true.false的转换. Java class Solution { public boolean parseBoolExpr(String expression) { Deque<Character> tfs = new ArrayDeque<

  • Java C++题解leetcode1620网络信号最好的坐标

    目录 题目 思路:暴力模拟 Java C++ Rust 题目 题目要求 思路:暴力模拟 因为数据范围小,所以是万万没想到的逐个遍历…… 遍历每个塔,然后找每个塔辐射的范围,用一个大矩阵记录每个点对应的信号大小,同时维护当前最大的信号及其对应坐标. Java class Solution { public int[] bestCoordinate(int[][] towers, int radius) { int[][] grid = new int[110][110]; int cx = 0,

  • 前端算法之TypeScript包含min函数的栈实例详解

    前端算法之TypeScript包含min函数的栈实例详解

    目录 前言 思路梳理 实现代码 示例代码 前言 基于数据结构: “栈”,实现一个min函数,调用此函数即可获取栈中的最小元素.在该栈中,调用min.push.pop的时间复杂度都是O(1). 本文就跟大家分享下这个算法,欢迎各位感兴趣的开发者阅读本文. 思路梳理 相信大多数开发者看到这个问题,第一反应可能是每次往栈中压入一个新元素时,将栈里的所有元素排序,让最小的元素位于栈顶,这样就能在O(1)的时间内得到最小元素了.但这种思路不能保证最后入栈的元素能够最先出栈,因此这个思路行不通. 紧接着,我

  • C语言之包含min函数的栈实例详解

    C语言之包含min函数的栈实例详解

    目录 一.题目描述 二.思路分析 三.整体代码 总结 一.题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中,调用 min.push 及 pop 的时间复杂度都是 O ( 1 ) \rm{O(1)} O(1). 示例: MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.min(); --> 返回-3. m

  • Python实现包含min函数的栈

    本文实例讲述了Python实现包含min函数的栈.分享给大家供大家参考,具体如下: # coding=utf8 ''' 题目:定义栈的数据结构,请在该类型中实现一个能够得到栈的最小元素的min函数. 在该栈中,调用min.push及pop的时间复杂度都是O(1). ''' class Stack(): def __init__(self): self.main_stack = [] # 辅助栈,每次次最小的元素压入辅助栈 self.assist_stack = [] # 记录栈中的最小元素 se

  • java算法题解Leetcode15三数之和实例

    目录 题目 解题思路 题目 15. 三数之和 给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组. 注意:答案中不可以包含重复的三元组. 示例 1:输入:nums = [-1,0,1,2,-1,-4]输出:[[-1,-1,2],[-1,0,1]]示例 2:输入:nums = []输出:[]示例 3:输入:nums = [0]输出:[]提示:0 <= nums.length <=

  • java算法题解牛客BM99顺时针旋转矩阵示例

    目录 题目描述 解题思路 实践代码 解法1 解法2 题目描述 BM99 顺时针旋转矩阵 描述 有一个NxN整数矩阵,请编写一个算法,将矩阵顺时针旋转90度. 给定一个NxN的矩阵,和矩阵的阶数N,请返回旋转后的NxN矩阵. 数据范围:0<n<300,矩阵中的值满足0≤val≤1000 要求:空间复杂度 O(N^2),时间复杂度 O(N^2) 进阶:空间复杂度 O(1),时间复杂度 O(N^2) 示例1输入:[[1,2,3],[4,5,6],[7,8,9]],3返回值:[[7,4,1],[8,5

  • Java C++题解leetcode消失的两个数字实例

    Java C++题解leetcode消失的两个数字实例

    目录 题目要求 思路:数学推导 Java C++ Rust 总结 题目要求 思路:数学推导 不重复的数组序列可以根据高斯公式计算所有元素的总和: 用当前数组长度加上两个缺失的数字可以得到所有数字长度,即可应用公式. 减去当前数组和即可得到缺失数字和sumsumsum: 两个缺失的数字分别位于m=sum2m=\frac{sum}{2}m=2sum两边: 遍历当前数组中所有小于(或大于)mmm的值,找到缺失的一个: 同样利用两个“和”的差值得到: 利用sumsumsum即可得到另一个. Java c

  • Java算法之最长公共子序列问题(LCS)实例分析

    Java算法之最长公共子序列问题(LCS)实例分析

    本文实例讲述了Java算法之最长公共子序列问题(LCS).分享给大家供大家参考,具体如下: 问题描述:一个给定序列的子序列是在该序列中删去若干元素后得到的序列.确切地说,若给定序列X= { x1, x2,-, xm},则另一序列Z= {z1, z2,-, zk}是X的子序列是指存在一个严格递增的下标序列 {i1, i2,-, ik},使得对于所有j=1,2,-,k有 Xij=Zj.例如,序列Z={B,C,D,B}是序列X={A,B,C,B,D,A,B}的子序列,相应的递增下标序列为{2,3,5,

  • 剑指Offer之Java算法习题精讲二叉树与斐波那契函数

    剑指Offer之Java算法习题精讲二叉树与斐波那契函数

    题目一 解法 class Solution { public int fib(int n) { int[] arr = new int[31]; arr[0] = 0; arr[1] = 1; for(int i = 2;i<=n;i++){ arr[i] = arr[i-2]+arr[i-1]; } return arr[n]; } } 题目二  解法 /** * Definition for a binary tree node. * public class TreeNode { * in

  • Java C++算法题解leetcode1592重新排列单词间的空格

    Java C++算法题解leetcode1592重新排列单词间的空格

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 模拟就完了 统计空格数量和单词数量,计算单词间应有的空格数,将它们依次放入结果字符串,若有余数则在末尾进行填补. Java class Solution { public String reorderSpaces(String text) { int n = text.length(), spcnt = 0; List<String> words = new ArrayList<>(); for (int

  • Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    Java C++ 算法题解leetcode1582二进制矩阵特殊位置

    目录 题目要求 思路:模拟 Java C++ Rust 题目要求 思路:模拟 直接按题意模拟,先算出每行每列中“111”的个数,然后判断统计行列值均为111的位置即可. Java class Solution { public int numSpecial(int[][] mat) { int n = mat.length, m = mat[0].length; int res = 0; int[] row = new int[n], col = new int[m]; for (int i =

随机推荐