算法

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).