FilesExpand file tree

 master

/

minStack.java

Copy path

BlameMore file actions

BlameMore file actions

Latest commit

 

History

History

History

57 lines (50 loc) · 1.56 KB

 master

/

minStack.java

Top

File metadata and controls

• Code
• Blame

57 lines (50 loc) · 1.56 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

import java.util.Stack;

/**

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

* push(x) -- 将元素 x 推入栈中

* pop() -- 删除栈顶的元素

* top() -- 获取栈顶元素

* getMin() -- 检索栈中的最小元素

*/

//看到题目第一想法是设置一个变量记录最小值，但是实现起来发现一旦栈结构发生改变要重新找最小值，不大好写然后看了解析利用辅助栈然后自己实现了一下

public class minStack {

private Stack<Integer> minStack;

private Stack<Integer> helper;

public minStack() {

minStack = new Stack<>();

helper = new Stack<>();

}

public void push(int x) {

minStack.push(x);

if (helper.isEmpty() || x < helper.peek()) {

helper.push(x);

} else {

helper.push(helper.peek());

}

}

public void pop() {

if (!minStack.isEmpty()) {

helper.pop();

minStack.pop();

}

}

public int getMin() {

if (!helper.isEmpty()) {

return helper.peek();

}

throw new RuntimeException("栈中元素为空,操作非法");

}

public int top() {

if (!minStack.isEmpty()) {

return minStack.peek();

}

throw new RuntimeException("栈中元素为空，操作非法");

}

public static void main(String[] args) {

minStack min = new minStack();

min.push(2);

min.push(6);

min.push(1);

System.out.println(min.getMin());

}

}