乡镇网站建设方案,广州哪家网站建设最好,享设计官网,陕西网站建设方案例题#xff1a; 分析#xff1a;
题目要求我们必须在常数时间内检索到最小元素。
我们可以使用两个栈#xff08;A、B#xff09;来实现#xff0c;A栈用来正常存储数据、弹出数据#xff0c; B栈用于存储A栈中的最小元素#xff0c;如下图#xff1a; 刚开始#…例题 分析
题目要求我们必须在常数时间内检索到最小元素。
我们可以使用两个栈A、B来实现A栈用来正常存储数据、弹出数据 B栈用于存储A栈中的最小元素如下图 刚开始 A栈没有数据 B栈先储存一个元素MAX整数最大值。 添加元素时 当向栈中加入数据时比如先加入元素 2 在A栈中直接存入 2 同时新加入元素与 B栈的栈顶元素比较把较小值加入B栈。保证在每次加入元素后B栈的栈顶是本次的最小元素。 弹出元素时 当弹出元素时A栈正常弹出元素同时B栈也要弹出元素 代码实现
package leetcodeup;import java.util.LinkedList;public class MinStackLeetcode155 {static class MinStack {private final LinkedListInteger stack new LinkedList();private final LinkedListInteger min new LinkedList();public MinStack() {min.push(Integer.MAX_VALUE);}public void push(int val) {stack.push(val);min.push(Math.min(val, min.peek()));}public void pop() {if(stack.isEmpty()){return;}stack.pop();min.pop();}public int top() {return stack.peek();}public int getMin() {return min.peek();}}
}这是求解这道题的第一种方法。 第二种方法
其实和第一种方法思路差不多我们可以把新添加元素和栈里面的最小元素一起加入栈中这样我们可以少用一个栈的空间。如下图
要存储这样的数据我们可以使用一种特殊的数据类型 -- record 它是JDK16引用的新语法
record 是一种新的关键字用于创建不可变的immutable数据类使用 record 关键字可以简化数据类的编写并自动提供许多常见的方法如 equals(), hashCode(), toString() 等。 record Data(int val, int min){ } 在上面的代码中我们定义了一个名为 Data的记录类它有两个字段 val和 min。由于这是一个 recordJava 会自动为这个类生成 equals(), hashCode(), toString(), 和一个构造函数。并为两个字段生成对应的get、set方法。 代码实现
static class MinStack2 {record Data(int val, int min){}private final LinkedListData stack new LinkedList();public void push(int val) {if(stack.isEmpty()){ //第一次添加新元素就是栈的最小值stack.push(new Data(val, val));}else{stack.push(new Data(val, Math.min(val, stack.peek().min)));}}public void pop() {stack.pop();}public int top() {return stack.peek().val;}public int getMin() {return stack.peek().min;}}
