FilesExpand file tree

 master

/

offer30.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

78 lines (68 loc) · 1.85 KB

 master

/

offer30.java

Copy path

Top

File metadata and controls

• Code
• Blame

78 lines (68 loc) · 1.85 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

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

import java.util.ArrayDeque;

import java.util.Deque;

/**

* [30] 包含 min 函数的栈

*

* 题目: 定义栈的数据结构, 请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中, 调用 min, push 及 pop 的时间复杂度都是 O(1).

*

* 思路: 使用辅助栈 min 存储当前的最小值.

*/

class MinStack {

private Deque<Integer> data;

private Deque<Integer> min;

/** initialize your data structure here. */

public MinStack() {

data = new ArrayDeque<>();

min = new ArrayDeque<>();

}

/**

* 方法一:

* 数据栈和最小值栈中元素个数相同.

*/

public void push1(int x) {

data.push(x);

// always push current minimum element into min stack.

if (!min.isEmpty() && min.peek() < x) min.push(min.peek());

else min.push(x);

}

public void pop1() {

data.pop();

min.pop();

}

/**

* 方法二:

* 数据栈中元素大于等于最小值栈中元素个数.

*/

public void push2(int x) {

data.push(x);

// push x into min stack,

// only when current insert value x is smaller or equal current minimum element.

if (min.isEmpty()) {

min.push(x);

} else if (x <= min.peek()) {

min.push(x);

}

}

public void pop2() {

int top = data.pop();

// when current pop element is equal min stack's top,

// pop min stack top element.

if (top == min.peek()) {

min.pop();

}

}

public int top() {

return data.peek();

}

public int min() {

return min.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();

*/