题目:

Suppose a sorted array is rotated at some pivot unknown to you beforehand.
(i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2).
Find the minimum element.
You may assume no duplicate exists in the array

基本上看到sorted, find, ... 这关键字就想到binary search二分查找.
根据输入 ...

Leetcode 上的题目, 实现一个Min Stack.
+ 带stack的一般功能, push, pop, top;
+ int getMin()能在constant time 返回最小值.

很明显, 带stack一般功能的容易实现, 用std::vector也行，or直接用std::stack<>这个container adapter更直接( 所谓adapter, 就是这个类型里面的实现会用到某些简单的container, 如vector, list).
但是那个getMin()呢?
假如只是取一个最小值, 那就简单了, 每次push时候都比较记录当前最小值就ok了. 但是假如不断地pop, 不断地getMin, 那stack内容改动了就需要不停地更新最小值.

一开始我想到保存一个最小值, 并可能需要O(n)的时间来更新这个最小值. 下面的方法是保存所有当前的最小值. 你只要取走了最小的, 然后下一个最小的立马出现了.

两个container, 其中一个是std::stack 用于实现一般的stack功能; 另一个可以是std::vector/list/stack ...

在书[Anany Levitin, 算法设计与分析基础]的第二章又看到汉诺塔的问题:
有三个柱子A B C; A柱上有好几个盘子, 小的放在大的上面;
现在问怎么把A柱上的盘子移到C柱上, B是做辅助的, 条件是大的盘子不能压到小的盘子上. 所以结果C柱上的盘子也是小的放在大的上面。

A,B,C; 三个柱子

假如A上有1个盘子，直接放到C上就解答完了。

假如A上有2个盘子ab，a盘小的 在 b盘大的上面. 先把a放到B上, b放到C上, 然后把a从B移到C上. 结果就是C柱上有ab。[pattern 1]
注意这种case中先把a放到C上, 那b放到B上, 然后a从C移到到B柱上, 那B柱上就有ab两个盘子了. 这结果很像上面的, 但是B柱跟C柱次序反了. 可见在移动盘子的时候, 柱子的次序, 是很重要的.

假如A上有3个盘子, 去尝试多画几次, 还是能解出来, 但是发现好像没有什么规律啊.
假如A上有4个盘子, 那可能就要尝试好多次才能碰巧一次解答出来. 还没有看出来规律.

要换一种角度来看啊, 上面我们已经解答了A柱上有2个盘子的case了. 那重新看A柱上有3个盘子的case.

A柱上的2个盘子 ...