程序员代码面试指南

发表于 | 分类于 |

《程序员代码面试指南 IT名企算法与数据结构题目最优解》题解

1.题目01

1550503434749

2.题解思路

  1. 方法一：

    如原书思路，设置两个栈stackData和stackMin，当前数据为data，先压入stackData，然后判断stackMin是否为空。

    如果为空，data压入stackMin中，如果不空，则比较data和stackMin栈顶元素。如果data小则入栈，否则stackMin的栈顶元素重复入栈。如图：

1550580837979

  1. 方法二：

    只用一个栈实现，在栈的类中添加返回最小值的方法。使用ArrayList来存储栈内元素，然后便利ArrayList返回栈中最小值。

3.代码实现

方法一：

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
package com.ITexercise;

import java.util.ArrayList;

public class MyStack {
	public static void main(String[] args) {
		ArrayList<Integer> array = new ArrayList<Integer>();
		MyStack stack =new MyStack();
		stack.push(array,1);
		stack.push(array, 2);
		stack.push(array, 5);
		stack.push(array, 6);
		printStack(array);
		System.out.println("--------------");
		
		stack.pop(array);
		printStack(array);
		System.out.println("--------------");
		
		
		System.out.println(stack.getMin(array));
	}

	public static void printStack(ArrayList<Integer> array) {
		for (int i = 0; i < array.size(); i++) {
			System.out.print(array.get(i)+"\t");
			}
	}
	
	public static boolean pop(ArrayList<Integer> array) {
		if (array.size() == 0) {
			return false;
		} else {
			array.remove(array.size() - 1);
			return true;
		}
	}

	public static boolean push(ArrayList<Integer> array, int data) {
		array.add(data);
		return true;
	}

	public static int getMin(ArrayList<Integer> array) {
		int min = array.get(0);
		for (int i = 0; i < array.size(); i++) {
			if (array.get(i) < min) {
				min = array.get(i);
			}
		}
		return min;
	}
}

方法二：

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
package com.ITexercise;

import java.util.Stack;

import javax.management.RuntimeErrorException;

public class MyStack2 {
	private Stack<Integer> stackData;
	private Stack<Integer> stackMin;
	
	public MyStack2() {
		this.stackData =new Stack<Integer>();
		this.stackMin = new Stack<Integer>();
	}
	
	public void push(int data) {
		if(this.stackMin.isEmpty()) {
			this.stackMin.push(data);
		}
		else if (data < this.stackMin.pop()) {
			this.stackMin.push(data);
		}
		else {
			this.stackMin.push(this.stackMin.pop());
		}
		stackData.push(data);
	}

	public int pop() {
		if(this.stackData.isEmpty()) {
			throw new RuntimeException("stack is empty");
		}
		else {
			this.stackMin.pop();
			return this.stackData.pop();
		}
	}
	
	public int getMin() {
		if(this.stackData.isEmpty()) {
			throw new RuntimeException("stack is empty");
		}
		return this.stackMin.peek();
	}
	
}

4.分析

方法一时间复杂度为O（1），空间复杂度为O（n）

方法二getMin（）时间复杂度为O（n），空间复杂度为O（n）

0%