程序员代码面试指南 001-020

020 打气球的最大分数

Problem and Solution
区间型动态规划虽然好想，但是状态不容易表示。假设已经打了i个气球，现在要打第i + 1个，在i个的基础上打任何一个都会得到i + 1个结果，肯定会出现同样的i + 1个但是分数不同的情况，这样只需要保留分数最大的就好了。如果用位向量表示气球是否被打掉，那么时间复杂度是指数级O(2 ^ n)，所以需要另外的表示方法。

考虑在第i次射击时打第s个气球，如果s左右两边的气球还没有被打掉，这种情况相当于第1次就打第s个，因为之前的射击完全不影响这次的分数，而影响这次分数的情况是s的左边或者右边有气球被打掉，所以应该根据已经射击的次数，将s左边打掉k个右边打掉i - k个的情况全部枚举出来，类似于将s作为长度为i的滑动窗口右端点，然后一直向右滑动直到s成为该窗口的左端点。扩展到所有s的情况，就可以理解为枚举整个数组中所有长度为i的区间，并以区间中每一个气球作为这一次的射击点，计算整个区间的最大值。

019 换钱的方法数

Problem and Solution
结合012和017即可。

018 最大值减去最小值小于或等于num的子数组数量

Problem and Solution
要求O(n)的空间复杂度和时间复杂度。对于枚举所有子数组的问题，通过固定上界变化下界或者固定下界变化上界可以实现O(n ^ 2)的复杂度，但是也需要继续优化。假如固定下界i，根据015的解法，可以算出和所有上界j组成的子数组的最大值和最小值，但是此时还需要变化上界j才可以找出所有的子数组。为了去掉这次遍历，j应该是立即可得的，所以应该对整个数组应用滑动窗口的方法，而不是某个固定的下界i。根据书上证明的性质，如果arr[i …… j]满足性质，那么其所有的子数组也满足性质，所以当出现上界j不满足性质时，可以一次性计算所有的子数组，最后递增i以固定新的下界。

017 机器人达到指定位置方法数

Problem and Solution
假设经过k步后机器人到达了位置n，那么下一步能到达的位置就是n - 1和n + 1，因此将每个位置左右两边的方法数求和即可。

016 求最大子矩阵的大小

Problem and Solution
首先想到的就是求以每个位置作为子矩阵右下角的最大面积，但是在从左向右的扫描过程中，不知道新的一列的高度取多少能达到最大值，需要反向查找前面的列，复杂度为O(n * m ^ 2)。或者先不管这一列，接着往右看。如果右面的比它小，那么这个高度肯定不能向右扩展了，至于左边，则可以一直扩展到比它小的那个，这样就把思路调整为以每个位置的高度作为子矩阵的高能得到的最大面积。

• 如果新的一列比左边高，那么向左肯定不能扩展了，但是向右也许还能，所以就先跳过这一列
• 如果新的一列比左边低，那么左边那一列肯定不能向右扩展了，至于向左，则可以一直扩展到第一个比它低的
• 如果新的一列和左边一样高，书上是按照第2种方式处理的（计算左边那一列一个没有意义的面积值）；这里的代码按照第1种处理的，跳过但是要保留更靠右的，如果保留更靠左的，在第2种情况中作为下界时就错了

015 生成窗口最大值数组

Problem and Solution
显然这题应该设计一个O(n)的算法。类似滑动窗口的思路，当窗口移动时，根据被剔除的元素和新加入的元素更新窗口的最大值，但是这个最大值该如何初始化需要进一步分析。

当加入第2个元素时，如果它比第1个元素大，那么需要更新最大值，同时因为窗口向后滑动，第1个元素在窗口内时，第2个元素肯定也在窗口内，所以就可以把第1个元素剔除了。如果第2个元素比第1个元素小，那么第2个元素可以作为下一个最大元素的候选值排在第1个元素后面。对于其它元素也采用这样的逻辑处理即可，所以应该是用双端队列来实现。

014 未排序数组中累加和小于或等于给定值的最长子数组长度

Problem and Solution
题目要求时间和空间复杂度都为O(n)，但是这种解法技巧性太强了。如果按照原来的方法，需要修改为查找累加和大于等于Sum[i] - k的最左位置，使用map中自带的lower_bound()即可，或者按照书上再生成一个helpArr。

本来是想用动态规划的，但是必须要用二维状态才能保证无后效性，即使是滚动数组也需要O(n * k)的时间复杂度，并且还不容易确定累加和的上限。

还是固定子数组的上界，变化下界以寻找最值。由于使用Sum[i]和Len[i]保存以i为结尾的最小和以及长度，所以下界不是递减，但是在最坏的情况下还是会退化成O(n ^ 2)。

013 用一个栈实现另一个栈的排序

Problem and Solution
只允许使用一个额外的栈，而栈只能进行push()和pop()操作，因此弹出的元素只能压入辅助栈中。可以在弹出的过程中单独保存最小值，这样一趟操作后找出了最小元素。更优化一点，可以不保存最小值，而是通过将辅助栈中的元素再放回原始栈中来为当前元素找一个正确的位置。

012 换钱的最少货币数

Problem and Solution
通过使用新面值的货币替换多张面值更小的货币，可以得到更小的货币数。假设使用前i种货币组合出了所有可能值，现在加入了第i + 1种货币，通过对已有组合值和新值进行结合，可以得到i + 1种货币所有可能的组合值，最后在组合之相同的情况下保留张数最小的即可。递推公式为Cnt[i][aim] = min(Cnt[i - 1][aim], Cnt[i][aim - arr[i]] + 1)。因为每种面值的货币可以用任意张，所以后一项是i而不是i - 1。

最终的结果不需要i，所以空间可以优化为只使用aim表示的这一维，新的递推公式为Cnt[aim] = min(Cnt[aim], Cnt[aim - arr[i]] + 1)。

011 未排序数组中累加和为给定值的最长子数组系列问题补2

Problem and Solution
改变上一题判断条件即可。

010 未排序数组中累加和为给定值的最长子数组系列问题补1

Problem and Solution
可以把上一题中的K看做0，正数计数递增，负数计数递减，0不变。

009 未排序数组中累加和为给定值的最长子数组长度

Problem and Solution
这道题是上一道题的进阶，数组中不仅有正数，还有负数和0。书上要求时间复杂度为O(N)，空间复杂度也为O(N)。但除非使用hash，否则时间负责度是O(NlogN)。

因为不能用滑动窗口的方法了，所以需要枚举所有的子数组，这会用掉O(N ^ 2)的时间，计算子数组和又是O(N)的时间，所以总共是O(N ^ 3)。通过优化枚举的方法，也就是固定下界变化上界或者固定上界变化下界，可以将时间优化为O(N ^ 2)。在这个基础上，可以将变化界的运算使用额外的存储代替，从而达到时间和空间都是O(N)。

• 固定下界i变化上界j，则子数组的和可以表示为i之后所有元素和与j之后所有元素和的差
• 固定上界j变化下界i，则子数组可以表示为前j个元素和与前i个元素和的差，注意要初始化前0个元素和为0

008 未排序正数数组中累加和为给定值的最长子数组的长度

Problem and Solution
要求O(N)的复杂度，所以只能进行一次遍历。因为数组中的元素都是正数，所以子数组越长和越大，越短和越小，根据这个特点，可以使用滑动窗口的方法进行一次遍历，找出和为K的最长子数组。

有两个注意点：

• 在sum == K的情况下，应该缩短左边界，否则就会死循环了
• end表示窗口的尾后元素，所以while循环应该是end <= N，并且在sum < K时，要根据end值判断是否扩大右边界

007 用递归函数和栈逆序一个栈

Problem and Solution
因为不允许用额外的存储空间，并且要用递归的方法，所以应该是先取出一个，然后逆序剩下的。因为栈只能在顶部操作，所以应该是取出栈底元素，逆序剩下的栈，最后压入栈底的元素。

这道题比较坑的是输出从栈底到栈顶输出。

006 由两个栈组成的队列

Problem and Solution
将入队的元素全部压入一个栈中，出队时将该栈中的元素全都弹出并压入另一个栈中，使用另一个栈执行出队操作。

005 设计getMin功能的栈

Problem and Solution
这好像是书上的第一道题，最开始看了半天没看懂。第一想法是把最小值存下来，但是只存一个还不行，万一这个被弹出了那下一个就找不到了，所以应该把最小值串起来。代码是书上第二种方法，用另一个栈同步存放最小值。当push()的值比最小值小时，就在最小栈中压入该值；否则就压入栈顶值。

004 不重复打印排序数组中相加和为给定值的所有三元组

Problem and Solution
找三元组也要求O(n ^ 2)的时间和O(1)的空间，可以借助二元组的解法，从左开始，依次选择三元组中第1个的元素，然后对后面的数组应用二元组的解法。每个元素只能用1次，三元组之间互不相同，三元组的第1个元素不能和第2个元素相同，但是第2个和第3个或许可以相同。

003 不重复打印排序数组中相加和为给定值的所有二元组

Problem and Solution
题目关于重复元素该如何处理都没说清楚，只能通过提交来试标准答案。

和下面的题很像。找二元组要求O(n)的时间和O(1)的空间，所以只能遍历一次，并且不能记录查找结果，所以必须要利用排序的性质——使用头尾指针向中间压缩即可。每个元素只能用1次，二元组之间不重复，二元组内两个元素或许可以重复。

002 最长的可整合子数组的长度

Problem and Solution
题目要求O(n ^ 2)的复杂度。使用二重循环将子数组枚举出来就已经够了，所以应该是在枚举的过程中就要判断是否可以整合。可整合的数组在排序后是一个公差为1的等差数列，因此直接判断子数组的极差是否和下标范围相等即可。

001 在行列都排好序的矩阵中找指定的数

Problem and Solution
题目要求O(m + n)的复杂度，也就是说最多遍历一行和一列。根据矩阵有序的特点，可以根据当前元素和K值的大小关系进行查找。从右上角和左下角查找应该都可以，因为两个方向的大小关系是不同的，而左上和右下就不行了。