min stack

题目

设计一个Stack,实现如下操作:

  1. push(), 入栈
  2. pop(), 出栈
  3. top(), 返回栈顶元素
  4. getMin(), 返回栈中的最小元素

注意上面的操作,都要在常数时间完成。

分析

Leetcode上面的原题,思路并不难想,但是AC还是有难度的,尤其是用Java,如果能够确保不出现MLE?我们先逐步分析一下。

首先,第一个思路,最容易想到,定义一个新的栈,栈的每一个元素包含两个数,一个当前数,一个入栈到目前为止的最小数。有如下的代码示例:

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
class Element {
public int x;
public int min;
public Element(int x, int min) {
super();
this.x = x;
this.min = min;
}
}
public class MinStackSlow {
private LinkedList<Element> stack = new LinkedList<Element>();
public void push(int x) {
int min = x;
if (!stack.isEmpty() && stack.getFirst().min < min)
min = stack.getFirst().min;
stack.addFirst(new Element(x, min));
}
public void pop() {
stack.removeFirst();
}
public int top() {
Element el = stack.getFirst();
return el.x;
}
public int getMin() {
return stack.getFirst().min;
}
}

代码很简单,但是MLE,内存超了。。。很不幸。那么如何优化呢?其实我们自己走一走这个过程,就会发现,在入栈出栈,以及getMin的过程中,有一些值,是不会出现在getMin中的。有一些min的数都是一样的。

那么我们浪费了空间来存储这些一样的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
47
48
49
class MinElement {
public int min;
public int freq;
public MinElement(int min, int freq) {
this.min = min;
this.freq = freq;
}
}
public class MinStack {
private LinkedList<Integer> stack = new LinkedList<Integer>();
private LinkedList<MinElement> min = new LinkedList<MinElement>();
public void push(int x) {
if (min.isEmpty()) {
min.addFirst(new MinElement(x, 1));
} else {
if (x == min.getFirst().min) {
min.getFirst().freq += 1;
} else if (x < min.getFirst().min) {
min.addFirst(new MinElement(x, 1));
}
}
stack.addFirst(x);
}
public void pop() {
int top = stack.removeFirst();
if (top == min.getFirst().min) {
if (min.getFirst().freq == 1) {
min.removeFirst();
} else {
min.getFirst().freq -= 1;
}
}
}
public int top() {
return stack.getFirst();
}
public int getMin() {
return min.getFirst().min;
}
}

提交之后,你会发现,代码还是有问题,人就是内存不过关,还能怎么优化呢?难道是LinkedList的问题?实际上,还真是这个问题。Java中LinkedList是一个双向的链表,实际上我们实现一个栈,只需要单向的。我们自己实现栈试试。代码比较糙,有些实现也不合规范。
但意思没问题,如下:

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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
package leetcode.min.stack;
class IntNode {
public int x;
public IntNode next;
public IntNode(int x, IntNode next) {
this.x = x;
this.next = next;
}
}
class IntStack {
private IntNode head;
public void push(int x) {
if (null == head) {
head = new IntNode(x, null);
} else {
IntNode newHead = new IntNode(x, head);
head = newHead;
}
}
public void pop() {
head = head.next;
}
public int top() {
return head.x;
}
}
class PairNode {
public int min;
public int freq;
public PairNode next;
public PairNode(int min, int freq, PairNode next) {
super();
this.min = min;
this.freq = freq;
this.next = next;
}
}
class PairStack {
private PairNode head;
public void push(int x) {
if (null == head) {
head = new PairNode(x, 1, null);
} else {
if (x == head.min) {
head.freq += 1;
} else if (x < head.min) {
PairNode newHead = new PairNode(x, 1, head);
head = newHead;
}
}
}
public void pop(int x) {
if (x == head.min) {
if (head.freq > 1) {
head.freq -= 1;
} else {
head = head.next;
}
}
}
public int top() {
return head.min;
}
}
public class SmallMemoryStack {
private IntStack stack = new IntStack();
private PairStack min = new PairStack();
public void push(int x) {
stack.push(x);
min.push(x);
}
public void pop() {
min.pop(stack.top());
stack.pop();
}
public int top() {
return stack.top();
}
public int getMin() {
return min.top();
}
}

通过了,看来问题确实如此。这也给了我们一个提醒,在实际的编码中,需要考虑的不仅仅是功能的实现,还有效率上的考虑。我们往往优先考虑时间,大多数时间考虑时间。但,空间也是同样重要的,尤其是Java这样的语言。

【完】

子数组最大乘积

题目

给定一个数组,至少有一个元素。请计算子数组最大乘积是多少?

例如:

  • 给定数组 [2, 3, -2, 4]
  • 经过计算,得到最大乘积为6。子数组为[2,3]。

题目来自Leetcode。

分析

这个题目,有经验的同学,看过一遍,就知道肯定是动态规划了,可具体要如何规划呢?我想,有的同学还记得子数组的最大和吧?是不是觉得很激动,O(n)就可以解决了。一样的思路!但是不好意思,错了!

错在哪里呢?乘法口诀还记得么?负负得正,就可恶在这里。在加法里,负负可得不到正。

Read More

最长01子串

最长01子串

原题

给定一个数组,数组中只包含0和1。请找到一个最长的子序列,其中0和1的数量是相同的。

例1:10101010 结果就是其本身。

例2:1101000 结果是110100

请大家展开自己的思路。

分析

这个题目,看起来比较简单,一些同学可能认为题目的描述符合动态规划的特征,然后就开始用动态规划解,努力找状态转移方程。这些同学的感觉,是很正确的。但,找状态转移方程,我们要对原来的数组进行变换一下。

原来是0和1的串,我们将0都换为-1。这样题目目标就变成,找到一个最长的子串,子串数字和是0。设原数组为A, DP[i]表示从0开始到i的子数组和。DP遍历一遍数组即可。例1中的数组产生的DP为:

0 1 2 3 4 5 6 7
1 0 1 0 1 0 1 0

这个例子,最后一个值是0,并且长度是偶数位。直接满足了结果。

再看例子2:

0 1 2 3 4 5 6
1 2 1 2 1 0 -1

5的位置为0,最长子串从0开始到5,长度为6。

上面这两个例子,所求的子串都是从头开始,如果不是从头开始,会是什么样的呢?看这个例子:1101100

0 1 2 3 4 5 6
1 2 1 2 3 2 1

通过观察上面的表格,我们可以得到,DP[0]==DP[6]==DP[2],DP[1]==DP[3]. 根据DP的定义,如果DP[i]==DP[j],i
一种方法,我们用map保存DP的值到位置的映射,如下表:

DP值 位置 最大位置 最小位置 最大长度
1 0,2,6 6 0 6
2 1,3 3 1 2
3 4 4 4 0
最长子串长度 6

我们最终的算法,要综合考虑最常穿是否从头开始的。
上面的这个思路,时间复杂度是O(n),空间复杂度也是O(n).

还有其他的思路,例如DP保存的是[0,i]的1的个数,那么DP[j] - DP[i] * 2 == j - i则表明A[i+1]…A[j]是一个满足条件的串,找到j-i最大的,就是最终的结果,这个思路的时间复杂度为O(n^2),空间复杂度为O(n).