非递归的方法——用栈来模拟整个过程

方法二：非递归的方法——用栈来模拟整个过程。

修改后的汉诺塔问题不能让任何塔从“左”直接移动到“右”，也不能从“右”直接移动到“左”，而是要经过中间。也就是说，实际动作只有4个：“左”到“中”、“中”到“左”、“中”到“右”、“右”到“中”。

现在我们把左、中、右三个地点抽象成栈，依次记为LS、MS和RS。最初所有的塔都在LS上。那么如上4个动作就可以看作是：某一个栈（from）把栈顶元素弹出，然后压入到另一个栈里（to），作为这一个栈（to）的栈顶。

例如，如果是7层塔，在最初时所有的塔都在LS上，LS从栈顶到栈底就依次是1～7，如果现在发生了“左”到“中”的动作，这个动作对应的操作是LS栈将栈顶元素1弹出，然后1压入到MS栈中，成为MS的栈顶。其他的操作同理。

一个动作能发生的先决条件是不违反小压大的原则。

from栈弹出的元素num如果想压入到to栈中，那么num的值必须小于当前to栈的栈顶。

还有一个原则不是很明显，但也是非常重要的，叫相邻不可逆原则，解释如下：

1．我们把四个动作依次定义为：L->M、M->L、M->R和R->M。

2．很明显，L->M和M->L过程互为逆过程，M->R和R->M互为逆过程。

3．在修改后的汉诺塔游戏中，如果想走出最少步数，那么任何两个相邻的动作都不是互为逆过程的。举个例子：如果上一步的动作是L->M，那么这一步绝不可能是M->L，直观地解释为：你上一步把一个栈顶数从“左”移动到“中”，这一步为什么又要移回去呢？这必然不是取得最小步数的走法。同理，M->R动作和R->M动作也不可能相邻发生。

有了小压大和相邻不可逆原则后，可以推导出两个十分有用的结论——非递归的方法核心结论：

1．游戏的第一个动作一定是L->M，这是显而易见的。

2．在走出最少步数过程中的任何时刻，四个动作中只有一个动作不违反小压大和相邻不可逆原则，另外三个动作一定都会违反。

对于结论2，现在进行简单的证明。

因为游戏的第一个动作已经确定是L->M，则以后的每一步都会有前一步的动作。

假设前一步的动作是L->M：

1．根据小压大原则，L->M的动作不会重复发生。

2．根据相邻不可逆原则，M->L的动作也不该发生。

3．根据小压大原则，M->R和R->M只会有一个达标。

假设前一步的动作是M->L：

1．根据小压大原则，M->L的动作不会重复发生。

2．根据相邻不可逆原则，L->M的动作也不该发生。

3．根据小压大原则，M->R和R->M只会有一个达标。

假设前一步的动作是M->R：

1．根据小压大原则，M->R的动作不会重复发生。

2．根据相邻不可逆原则，R->M的动作也不该发生。

3．根据小压大原则，L->M和M->L只会有一个达标。

假设前一步的动作是R->M：

1．根据小压大原则，R->M的动作不会重复发生。

2．根据相邻不可逆原则，M->R的动作也不该发生。

3．根据小压大原则，L->M和M->L只会有一个达标。

综上所述，每一步只会有一个动作达标。那么只要每走一步都根据这两个原则考查所有的动作就可以，哪个动作达标就走哪个动作，反正每次都只有一个动作满足要求，按顺序走下来即可。

非递归的具体过程请参看如下代码中的hanoiProblem2方法。

public enum Action { No, LToM, MToL, MToR, RToM } public int hanoiProblem2(int num, String left, String mid, String right) { StacklS = new Stack(); StackmS = new Stack(); StackrS = new Stack(); lS.push(Integer.MAX_VALUE); mS.push(Integer.MAX_VALUE); rS.push(Integer.MAX_VALUE); for (int i = num; i > 0; i--) { lS.push(i); } Action[] record = { Action.No }; int step = 0; while (rS.size() ! = num + 1) { step += fStackTotStack(record, Action.MToL, Action.LToM, lS, mS, left, mid); step += fStackTotStack(record, Action.LToM, Action.MToL, mS, lS, mid, left); step += fStackTotStack(record, Action.RToM, Action.MToR, mS, rS, mid, right); step += fStackTotStack(record, Action.MToR, Action.RToM, rS, mS, right, mid); } return step; } public static int fStackTotStack(Action[] record, Action preNoAct, Action nowAct, StackfStack, StacktStack, String from, String to) { if (record[0] ! = preNoAct && fStack.peek() < tStack.peek()) { tStack.push(fStack.pop()); System.out.println("Move " + tStack.peek() + " from " + from + " to " + to); record[0] = nowAct; return 1; } return 0; }

生成窗口最大值数组

【题目】

有一个整型数组arr和一个大小为w 的窗口从数组的最左边滑到最右边，窗口每次向右边滑一个位置。

例如，数组为[4，3，5，4，3，3，6，7]，窗口大小为3时：

[4 3 5] 4 3 3 6 7 窗口中最大值为5 4 [3 5 4] 3 3 6 7 窗口中最大值为5 4 3 [5 4 3] 3 6 7 窗口中最大值为5 4 3 5 [4 3 3] 6 7 窗口中最大值为4 4 3 5 4 [3 3 6] 7 窗口中最大值为6 4 3 5 4 3 [3 6 7] 窗口中最大值为7

如果数组长度为n ，窗口大小为w ，则一共产生n -w +1个窗口的最大值。

请实现一个函数。

●　输入：整型数组arr，窗口大小为w 。

●　输出：一个长度为n -w +1的数组res，res[i]表示每一种窗口状态下的最大值。

以本题为例，结果应该返回{5，5，5，4，6，7}。

【难度】

尉　★★☆☆

【解答】

如果数组长度为N ，窗口大小为w ，如果做出时间复杂度O (N ×w )的解法是不能让面试官满意的，本题要求面试者想出时间复杂度O (N )的实现。

本题的关键在于利用双端队列来实现窗口最大值的更新。首先生成双端队列qmax，qmax中存放数组arr中的下标。

假设遍历到arr[i]，qmax的放入规则为：

1．如果qmax为空，直接把下标i放进qmax，放入过程结束。

2．如果qmax不为空，取出当前qmax队尾存放的下标，假设为j。

1）如果arr[j]>arr[i]，直接把下标i放进qmax的队尾，放入过程结束。

2）如果arr[j]<=arr[i]，把j从qmax中弹出，继续qmax的放入规则。

假设遍历到arr[i]，qmax的弹出规则为：

如果qmax队头的下标等于i-w，说明当前qmax队头的下标已过期，弹出当前对头的下标即可。

根据如上的放入和弹出规则，qmax便成了一个维护窗口为w 的子数组的最大值更新的结构。下面举例说明题目给出的例子。

1．开始时qmax为空，qmax={}

2．遍历到arr[0]==4，将下标0放入qmax，qmax={0}。

3．遍历到arr[1]==3，当前qmax的队尾下标为0，又有arr[0]>arr[1]，所以将下标1放入qmax的尾部，qmax={0，1}。

4．遍历到arr[2]==5，当前qmax的队尾下标为1，又有arr[1]<=arr[2]，所以将下标1从qmax的尾部弹出，qmax变为{0}。当前qmax的队尾下标为0，又有arr[0]<=arr[2]，所以将下标0从qmax尾部弹出，qmax变为{}。将下标2放入qmax，qmax={2}。此时已经遍历到下标2的位置，窗口arr[0..2]出现，当前qmax队头的下标为2，所以窗口arr[0..2]的最大值为arr[2]（即5）。

5．遍历到arr[3]==4，当前qmax的队尾下标为2，又有arr[2]>arr[3]，所以将下标3放入qmax尾部，qmax={2，3}。窗口arr[1..3]出现，当前qmax队头的下标为2，这个下标还没有过期，所以窗口arr[1..3]的最大值为arr[2]（即5）。

6．遍历到arr[4]==3，当前qmax的队尾下标为3，又有arr[3]>arr[4]，所以将下标4放入qmax尾部，qmax={2，3，4}。窗口arr[2..4]出现，当前qmax队头的下标为2，这个下标还没有过期，所以窗口arr[2..4]的最大值为arr[2]（即5）。

7．遍历到arr[5]==3，当前qmax的队尾下标为4，又有arr[4]<=arr[5]，所以将下标4从qmax的尾部弹出，qmax变为{2，3}。当前qmax的队尾下标为3，又有arr[3]>arr[5]，所以将下标5放入qmax尾部，qmax={2，3，5}。窗口arr[3..5]出现，当前qmax队头的下标为2，这个下标已经过期，所以从qmax的头部弹出，qmax变为{3，5}。当前qmax队头的下标为3，这个下标没有过期，所以窗口arr[3..5]的最大值为arr[3]（即4）。

8．遍历到arr[6]==6，当前qmax的队尾下标为5，又有arr[5]<=arr[6]，所以将下标5从qmax的尾部弹出，qmax变为{3}。当前qmax的队尾下标为3，又有arr[3]<=arr[6]，所以将下标3从qmax的尾部弹出，qmax变为{}。将下标6放入qmax，qmax={6}。窗口arr[4..6]出现，当前qmax队头的下标为6，这个下标没有过期，所以窗口arr[4..6]的最大值为arr[6] （即6）。

9．遍历到arr[7]==7，当前qmax的队尾下标为6，又有arr[6]<=arr[7]，所以将下标6从qmax的尾部弹出，qmax变为{}。将下标7放入qmax，qmax={7}。窗口arr[5..7]出现，当前qmax队头的下标为7，这个下标没有过期，所以窗口arr[5..7]的最大值为arr[7] （即7）。

10．依次出现的窗口最大值为[5，5，5，4，6，7]，在遍历过程中收集起来，最后返回即可。

上述过程中，每个下标值最多进qmax一次，出qmax一次。所以遍历的过程中进出双端队列的操作是时间复杂度为O (N )，整体的时间复杂度也为O (N )。具体过程参看如下代码中的getMaxWindow方法。

public int[] getMaxWindow(int[] arr, int w) { if (arr == null || w < 1 || arr.length < w) { return null; } LinkedListqmax = new LinkedList(); int[] res = new int[arr.length - w + 1]; int index = 0; for (int i = 0; i < arr.length; i++) { while (! qmax.isEmpty() && arr[qmax.peekLast()] <= arr[i]) {

qmax.pollLast(); } qmax.addLast(i); if (qmax.peekFirst() == i - w) { qmax.pollFirst(); } if (i >= w - 1) { res[index++] = arr[qmax.peekFirst()]; } } return res; }