首页 > 其他 > 详细

9.17 最小栈 简单

时间:2019-09-17 10:21:30      阅读:26      评论:0      收藏:0      [点我收藏+]

标签:bubuko   exc   支持   urn   元素   示例   

技术分享图片

 

 题目:

 

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

 

push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。
示例:

 

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

 

代码:

 

 1 class MinStack {
 2 
 3     /** initialize your data structure here. */
 4     private int stackSize = 1000;
 5     private int top = 0;
 6     private int base = 0;
 7     private int[] stack;
 8     public MinStack() {
 9         stack = new int[stackSize];
10     }
11     
12     public void push(int x) {
13         if(top < stackSize){
14             stack[top++] = x;
15         }
16     }
17     
18     public void pop() {
19         top--;
20     }
21     
22     public int top() {
23         if(top != 0){
24             return stack[top - 1];  
25         }
26         throw new RuntimeException();
27     }
28     public int getMin(){
29         int save = Integer.MAX_VALUE;
30         for(int i = 0; i < top; i++){
31             if(stack[i] < save)
32                 save = stack[i];
33         }
34         return save;
35     }
36 }
37 
38 /**
39  * Your MinStack object will be instantiated and called as such:
40  * MinStack obj = new MinStack();
41  * obj.push(x);
42  * obj.pop();
43  * int param_3 = obj.top();
44  * int param_4 = obj.getMin();
45  */

 

心得:

1、这道题的做法是很简单的,就是让你写出栈的几个基本方法;

2、这里运用了一个自己写的顺序栈,但是时间、空间复杂度都很高,过后再进行修改;

9.17 最小栈 简单

标签:bubuko   exc   支持   urn   元素   示例   

原文:https://www.cnblogs.com/wasi-991017/p/11531463.html

(0)
(0)
   
举报
评论 一句话评论(0
登录后才能评论!
© 2014 bubuko.com 版权所有 鲁ICP备09046678号-4
打开技术之扣,分享程序人生!
             

鲁公网安备 37021202000002号