剑指 Offer 30. 包含min函数的栈

Posted on | In
Words count in article: 452 | Reading time ≈ 2

题目

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

示例 1:

1
2
3
4
5
6
7
8
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 次

解法

解法一：

JAVA

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
class MinStack {

    private Stack<Integer> data;
	private Stack<Integer> helper;

	public MinStack() {
		data = new Stack<>();
		helper = new Stack<>();
	}

	public void push(int x) {
		data.add(x);
		if (helper.isEmpty() || helper.peek() >= x) {
			helper.add(x);
		}
	}

	public void pop() {
		if (!data.isEmpty()) {
			int top = data.pop();
			if (top == helper.peek()) {
				helper.pop();
			}
		}
	}

	public int top() {
		if (!data.isEmpty()) {
			return data.peek();
		}
		throw new RuntimeException("Empty stack");
	}

	public int min() {
		if (!helper.isEmpty()) {
			return helper.peek();
		}
		throw new RuntimeException("Empty stack");
	}
}

解法二：

超时

Java

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
public int[] spiralOrder(int[][] matrix) {

        if (Objects.isNull(matrix)) {
            return null;
        }
        
        if (0 == matrix.length) {
            return new int[]{};
        }

        int[][] directions = new int[4][2];
        directions[0] = new int[]{0, 1};     // x++;
        directions[1] = new int[]{1, 0};     // y++;
        directions[2] = new int[]{0, -1};     // x--;
        directions[3] = new int[]{-1, 0};     // y--

        int[] result = new int[matrix.length * matrix[0].length];
        int index = 0;
        Set<String> visited = new HashSet<>(result.length);
        int row = matrix.length;
        int col = matrix[0].length;
        int directionIndex = 0;
        int r = 0;
        int c = 0;
        while (index < result.length) {
            String p = r + "_" + c;
            if (visited.contains(p)) {
                continue;
            }

            result[index++] = matrix[r][c];

            if (directionIndex == 0 && (c + 1) == col) {
                // 转向
                directionIndex = (directionIndex + 1) % 4;
            } else if (directionIndex == 1 && (r + 1) == row) {
                // 转向
                directionIndex = (directionIndex + 1) % 4;
            } else if (directionIndex == 2 && (c == 0 || visited.contains(p))) {
                // 转向
                directionIndex = (directionIndex + 1) % 4;
            } else if (directionIndex == 3 && (r == 0 || visited.contains((r - 1) + "_" + c))) {
                // 转向
                directionIndex = 0;
            }
            r += directions[directionIndex][0];
            c += directions[directionIndex][1];
            visited.add(p);
        }
        return result;
    }
0%