第一章：栈和队列（三）
单调栈结构
【题目】
给定一个不含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。返回所有位置相应的信息。
【举例】
arr = {3,4,1,5,6,2,7}
返回如下二维数组作为结果：
{
{-1, 2},
{ 0, 2},
{-1,-1},
{ 2, 5},
{ 3, 5},
{ 2,-1},
{ 5,-1}
}
-1表示不存在。所以上面的结果表示在arr中，0位置左边和右边离0位置最近且值比arr[0]小的位置是-1和2；1位置左边和右边离1位置最近且值比arr[1]小的位置是0和2；2位置左边和右边离2位置最近且值比arr[2]小的位置是-1和-1……
进阶问题：给定一个可能含有重复值的数组arr，找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置。返回所有位置相应的信息。
【要求】
如果arr长度为N，实现原问题和进阶问题的解法，时间复杂度都达到O(N)。
【难度】
尉★★☆☆
【解答】
public int[][] rightWay(int[] arr) {
int[][] res = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) {
int leftLessIndex = -1;
int rightLessIndex = -1;
int cur = i - 1;
while (cur >= 0) {
if (arr[cur] < arr[i]) {
leftLessIndex = cur;
break;
}
cur--;
}
cur = i + 1;
while (cur < arr.length) {
if (arr[cur] < arr[i]) {
rightLessIndex = cur;
break;
}
cur++;
}
res[i][0] = leftLessIndex;
res[i][1] = rightLessIndex;
}
return res;
}
关键在于生成所有位置的相应信息，时间复杂度做到O(N)，这需要用到单调栈结构，这个结构在算法面试中经常出现，本章还用单调栈结构解决了几个问题，请读者好好掌握这种结构。首先解决原问题，也就是没有重复值的数组如何使用单调栈解决这个问题，然后看看可能含有重复值的数组如何使用单调栈。
原问题：准备一个栈，记为stack<Integer>，栈中放的元素是数组的位置，开始时stack为空。如果找到每一个i位置左边和右边离i位置最近且值比arr[i]小的位置，那么需要让stack从栈顶到栈底的位置所代表的值是严格递减的；如果找到每一个i位置左边和右边离i位置最近且值比arr[i]大的位置，那么需要让stack从栈顶到栈底的位置所代表的值是严格递增的。本题需要解决的是前者，但是对于后者，原理完全是一样的。
下面用例子来展示单调栈的使用和求解流程，初始时arr = {3,4,1,5,6,2,7}，stack从栈顶到栈底为：{}；
遍历到arr[0]==3，发现stack为空，就直接放入0位置。stack从栈顶到栈底为：{0位置(值是3)}；
遍历到arr[1]==4，发现直接放入1位置，不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为：{1位置(值是4)、0位置(值是3)}；
遍历到arr[2]==1，发现直接放入2位置（值是1），会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，所以从stack开始弹出位置。如果x位置被弹出，在栈中位于x位置下面的位置，就是x位置左边离x位置最近且值比arr[x]小的位置；当前遍历到的位置就是x位置右边离x位置最近且值比arr[x]小的位置。从stack弹出位置1，在栈中位于1位置下面的是位置0，当前遍历到的是位置2，所以ans[1]={0,2}。弹出1位置之后，发现放入2位置（值是1）还会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，所以继续弹出位置0。在栈中位于位置0下面已经没有位置了，说明在位置0左边不存在比arr[0]小的值，当前遍历到的是位置2，所以ans[0]={-1,2}。stack已经为空，所以放入2位置（值是1），stack从栈顶到栈底为：{2位置(值是1)}；
遍历到arr[3]==5，发现直接放入3位置，不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为：{3位置(值是5)、2位置(值是1)}；
遍历到arr[4]==6，发现直接放入4位置，不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为：{4位置(值是6)、3位置(值是5)、2位置(值是1)}；
遍历到arr[5]==2，发现直接放入5位置，会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，所以开始弹出位置。弹出位置4，栈中它的下面是位置3，当前是位置5，ans[4]={3,5}。弹出位置3，栈中它的下面是位置2，当前是位置5，ans[3]={2,5}。然后放入5位置就不会破坏stack的单调性了。stack从栈顶到栈底依次为：{5位置(值是2)、2位置(值是1)}；
遍历到arr[6]==7，发现直接放入6位置，不会破坏stack从栈顶到栈底的位置所代表的值是严格递减的，那么直接放入。stack从栈顶到栈底依次为：{6位置(值是7)、5位置(值是2)、2位置(值是1)}。
遍历阶段结束后，清算栈中剩下的位置。
弹出6位置，栈中它的下面是位置5，6位置是清算阶段弹出的，所以ans[6]={5,-1}；
弹出5位置，栈中它的下面是位置2，5位置是清算阶段弹出的，所以ans[5]={2,-1}；
弹出2位置，栈中它的下面没有位置了，2位置是清算阶段弹出的，所以ans[2]={-1,-1}。
至此，已经全部生成了每个位置的信息。请读者再熟悉一下上面的流程，下面证明在单调栈中，如果x位置被弹出，在栈中位于x位置下面的位置为什么就是x位置左边离x位置最近且值比arr[x]小的位置；当前遍历到的位置就是x位置右边离x位置最近且值比arr[x]小的位置。假设stack当前栈顶位置是x，值是5；x下面是i位置，值是1；当前遍历到j位置，值是4。如图1-6所示，请注意整个数组中是没有重复值的。
当前来到j位置，但是x位置已经在栈中，所以x位置肯定在j位置的左边：……5（x位置）……4（j位置）……。如果在5和4之间存在小于5的数，那么没等遍历到当前的4，x位置（值是5）就已经被弹出了，轮不到当前位置的4来让x位置的5弹出，所以5和4之间的数要么没有，要么一定比5大，所以x位置右边离x位置最近且小于arr[x]的位置就是j位置。
当前弹出的是x位置，x位置下面的是位置i，i比x早进栈，所以i位置肯定在x位置的左边：……1（i位置）……5（x位置）……。如果在1和5之间存在小于1的数，那么i位置（值是1）会被提前弹出，在栈中i位置和x位置就不可能贴在一起。如果在1和5之间存在大于1但小于5的数，那么在栈中i位置和x位置之间一定会夹上一个别的位置，也不可能贴在一起。所以1和5之间的数要么没有，要么一定比5大，那么x位置左边离x位置最近且小于arr[x]的位置就是i位置。
public int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
Stack<Integer> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int popIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = i;
}
stack.push(i);
}
while (!stack.isEmpty()) {
int popIndex = stack.pop();
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][0] = leftLessIndex;
res[popIndex][1] = -1;
}
return res;
} 进阶问题，可能含有重复值的数组如何使用单调栈。其实整个过程和原问题的解法差不多。举个例子来说明，初始时arr={3,1,3,4,3,5,3,2,2}，stack从栈顶到栈底为：{}；
遍历到arr[0]==3，发现stack为空，就直接放入0位置。stack从栈顶到栈底为：{0位置(值是3)}；
遍历到arr[1]==1，从栈中弹出位置0，并且得到ans[0]={-1,1}。位置1进栈，stack从栈顶到栈底为：{1位置(值是1)}；
遍历到arr[2]==3，发现位置2可以直接放入。stack从栈顶到栈底依次为：{2位置(值是3)、1位置(值是1)}；
遍历到arr[3]==4，发现位置3可以直接放入。stack从栈顶到栈底依次为：{3位置(值是4)、2位置(值是3)、1位置(值是1)}；
遍历到arr[4]==3，从栈中弹出位置3，并且得到ans[3]={2,4}。此时发现栈顶是位置2，值是3，当前遍历到位置4，值也是3，所以两个位置压在一起。stack从栈顶到栈底依次为：{ [2位置, 4位置](值是3)、1位置(值是1)}；
遍历到arr[5]==5，发现位置5可以直接放入。stack从栈顶到栈底依次为：{ 5位置(值是5)、[2位置, 4位置](值是3)、1位置(值是1)}；
遍历到arr[6]==3，从栈中弹出位置5，在栈中位置5的下面是[2位置, 4位置]，选最晚加入的4位置，当前遍历到位置6，所以得到ans[5]={4,6}。位置6进栈，发现又是和栈顶位置代表的值相等的情况，所以继续压在一起，stack从栈顶到栈底依次为：{ [2位置, 4位置, 6位置](值是3)、1位置(值是1)}；
遍历到arr[7]==2，从栈中弹出[2位置, 4位置, 6位置]，在栈中这些位置下面的是1位置，当前是7位置，所以得到ans[2]={1,7}、ans[4]={1,7}、ans[6]={1,7}。位置7进栈，stack从栈顶到栈底依次为：{7位置(值是2)、1位置(值是1)}；
遍历到arr[8]==2，发现位置8可以直接进栈，并且又是相等的情况，stack从栈顶到栈底依次为：{[7位置, 8位置](值是2)、1位置(值是1)}。
遍历完成后，开始清算阶段：
弹出[7位置, 8位置]，生成ans[7]={1,-1}、ans[8]={1,-1}；
弹出1位置，生成ans[1]={-1,-1}。
public int[][] getNearLess(int[] arr) {
int[][] res = new int[arr.length][2];
Stack<List<Integer>> stack = new Stack<>();
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List<Integer> popIs = stack.pop();
// 取位于下面位置的列表中，最晚加入的那个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
stack.peek().size() - 1);
for (Integer popi : popIs) {
res[popi][0] = leftLessIndex;
res[popi][1] = i;
}
}
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
stack.peek().add(Integer.valueOf(i));
} else {
ArrayList<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
while (!stack.isEmpty()) {
List<Integer> popIs = stack.pop();
// 取位于下面位置的列表中，最晚加入的那个
int leftLessIndex = stack.isEmpty() ? -1 : stack.peek().get(
stack.peek().size() - 1);
for (Integer popi : popIs) {
res[popi][0] = leftLessIndex;
res[popi][1] = -1;
}
}
return res;
}
求最大子矩阵的大小
【题目】
给定一个整型矩阵map，其中的值只有0和1两种，求其中全是1的所有矩形区域中，最大的矩形区域为1的数量。
例如：
1 1 1 0
其中，最大的矩形区域有3个1，所以返回3。
再如：
1 0 1 1
1 1 1 1
1 1 1 0
其中，最大的矩形区域有6个1，所以返回6。
【难度】
校 ★★★☆
【解答】
如果矩阵的大小为O(N´M)，可以做到时间复杂度为O(N´M)。解法的具体过程如下。
1．矩阵的行数为N，以每一行做切割，统计以当前行作为底的情况下，每个位置往上的1的数量。使用高度数组height来表示。
例如：
map = 1 0 1 1
1 1 1 1
1 1 1 0
以第1行做切割后，height={1,0,1,1}，height[j]表示在目前的底（第1行）的j位置往上（包括j位置），有多少个连续的1。
以第2行做切割后，height={2,1,2,2}，height[j]表示在目前的底（第2行）的j位置往上（包括j位置），有多少个连续的1。注意到从第一行到第二行，height数组的更新是十分方便的，即height[j] = map[i][j]==0 ? 0 : height[j]+1。
以第3行做切割后，height={3,2,3,0}，height[j]表示在目前的底（第3行）的j位置往上（包括j位置），有多少个连续的1。
2．对于每一次切割，都利用更新后的height数组来求出以当前行为底的情况下，最大的矩形是什么。那么这么多次切割中，最大的那个矩形就是我们要的答案。
整个过程就是如下代码中的maxRecSize方法。步骤2的实现是如下代码中的maxRecFromBottom方法。
下面重点介绍一下步骤2如何快速地实现，这也是这道题最重要的部分，如果height数组的长度为M，那么求解步骤2的过程可以做到时间复杂度为O(M)。
对于height数组，读者可以理解为一个直方图，比如{3,2,3,0}，其实就是如图1-7所示的直方图。
也就是说，步骤2的实质是在一个大的直方图中求最大矩形的面积。如果我们能够求出以每一根柱子扩展出去的最大矩形，那么其中最大的矩形就是我们想找的。比如：
— 第1根高度为3的柱子向左无法扩展，它的右边是2，比3小，所以向右也无法扩展，则以第1根柱子为高度的矩形面积就是3*1==3；
— 第2根高度为2的柱子向左可以扩1个距离，因为它的左边是3，比2大；右边的柱子也是3，所以向右也可以扩1个距离，则以第2根柱子为高度的矩形面积就是2*3==6；
— 第3根高度为3的柱子向左没法扩展，向右也没法扩展，则以第3根柱子为高度的矩形面积就是3*1==3；
— 第4根高度为0的柱子向左没法扩展，向右也没法扩展，则以第4根柱子为高度的矩形面积就是0*1==0；
所以，当前直方图中最大的矩形面积就是6，也就是图1-7中虚线框住的部分。
考查每一根柱子最大能扩多大，这个行为的实质就是找到柱子左边离它最近且比它小的柱子位置在哪里，以及右边离它最近且比它小的柱子位置在哪里。这个过程怎么计算最快呢？利用单调栈，这个内容请读者先阅读本书的“单调栈结构”问题，并彻底理解该结构。
为了方便表述，我们以height={3,4,5,4,3,6}为例说明如何根据height数组求其中的最大矩形。具体过程如下：
1．生成一个栈，记为stack，从左到右遍历height数组，每遍历一个位置，都会把位置压进stack中。
2．遍历到height的0位置，height[0]=3，此时stack为空，直接将位置0压入栈中，此时stack从栈顶到栈底为{0}。
3．遍历到height的1位置，height[1]=4，此时stack的栈顶为位置0，值为height[0]=3，又有height[1]>height[0]，那么将位置1直接压入stack。这一步体现了遍历过程中的一个关键逻辑：只有当前i位置的值height[i]大于当前栈顶位置所代表的值（height[stack.peek()]），则i位置才可以压入stack。
所以可以知道，stack中从栈顶到栈底的位置所代表的值是依次递减，并且无重复值，此时stack从栈顶到栈底为{1,0}。
4．遍历到height的2位置，height[2]=5，与步骤3的情况完全一样，所以直接将位置2压入stack，此时stack从栈顶到栈底为{2,1,0}。
5．遍历到height的3位置，height[3]=4，此时stack的栈顶为位置2，值为height[2]=5，又有height[3]<height[2]。此时又出现了一个遍历过程中的关键逻辑，即如果当前i位置的值height[i]小于或等于当前栈顶位置所代表的值（height[stack.peek()]），则把栈中存的位置不断弹出，直到某一个栈顶所代表的值小于height[i]，再把位置i压入，并在这期间做如下处理：
1）假设当前弹出的栈顶位置记为位置j，弹出栈顶之后，新的栈顶记为k。然后开始考虑位置j的柱子向右和向左最远能扩到哪里。
2）对位置j的柱子来说，向右最远能扩到哪里呢？
如果height[j]>height[i]，那么i-1位置就是向右能扩到的最远位置。j之所以被弹出，就是因为遇到了第一个比j位置值小的位置。
如果height[j]==height[i]，那么i-1位置不一定是向右能扩到的最远位置，只是起码能扩到的位置。那怎么办呢？
可以肯定的是，在这种情况下，i位置的柱子向左必然也可以扩到j位置。也就是说，j位置的柱子扩出来的最大矩形和i位置的柱子扩出来的最大矩形是同一个。
所以，此时j位置的柱子能扩出来的最大矩形虽然无法被正确计算，但不要紧，因为i位置肯定要压入到栈中，那么j位置和i位置共享的最大矩形就等i位置弹出的时候再计算即可。
3）对位置j的柱子来说，向左最远能扩到哪里呢？
根据单调栈的性质，k位置的值是j位置的值左边离j位置最近的比j位置的值小的位置，所以j位置的柱子向左最远可以扩到k+1位置。
4）综上所述，j位置的柱子能扩出来的最大矩形为(i-k-1)*height[j]。
以例子来说明。
① i==3，height[3]=4，此时stack的栈顶为位置2，值为height[2]=5，故height[3]<= height[2]，所以位置2被弹出（j==2），当前栈顶变为1（k==1）。位置2的柱子扩出来的最大矩形面积为(3-1-1)*5==5。
② i==3，height[3]=4，此时stack的栈顶为位置1，值为height[1]=4，故height[3]<=height[1]，所以位置1被弹出（j==1），当前栈顶变为1（k==0）。位置1的柱子扩出来的最大矩形面积为(3-0-1)*4==8，这个值实际上是不对的（偏小），但在位置3被弹出的时候是能够重新正确计算得到的。
③ i==3，height[3]=4，此时stack的栈顶为位置0，值为height[0]=3，这时height[3]<=height[2]，所以位置0不弹出。
④将位置3压入stack，stack从栈顶到栈底为{3,0}。
6．遍历到height的4位置，height[4]=3。与步骤5的情况类似，以下是弹出过程：
1）i==4，height[4]=3，此时stack的栈顶为位置3，值为height[3]=4，故height[4]<=height[3]，所以位置3被弹出（j==3），当前栈顶变为0（k==0）。位置3的柱子扩出来的最大矩形面积为(4-0-1)*4==12。这个最大面积也是位置1的柱子扩出来的最大矩形面积，在位置1被弹出时，这个矩形其实没有找到，但在位置3这里找到了。
2）i==4，height[4]=3，此时stack的栈顶为位置0，值为height[0]=3，故height[4]<=height[0]，所以位置0被弹出（j==0），当前没有了栈顶元素，此时可以认为k==-1。位置0的柱子扩出来的最大矩形面积为(4-(-1)-1)*3==12，这个值实际上是不对的（偏小），但在位置4被弹出时是能够重新正确计算得到的。
3）栈已经为空，所以将位置4压入stack，此时从栈顶到栈底为{4}。
7．遍历到height的5位置，height[5]=6，情况和步骤3类似，直接压入位置5，此时从栈顶到栈底为{5,4}。
8．遍历结束后，stack中仍有位置没有经历扩的过程，从栈顶到栈底为{5,4}。此时因为height数组再往右不能扩出去，所以认为i==height.length==6且越界之后的值极小，然后开始弹出留在栈中的位置：
1）i==6，height[6]极小，此时stack的栈顶为位置5，值为height[5]=6，故height[6]<=height[5]，所以位置5被弹出（j==5），当前栈顶变为4（k==4）。位置5的柱子扩出来的最大矩形面积为(6-4-1)*6==6。
2）i==6，height[6]极小，此时stack的栈顶为位置4，值为height[4]=3，故height[6]<=height[4]，所以位置4被弹出（j==4），栈空了，此时可以认为k==-1。位置4的柱子扩出来的最大矩形面积为(6-(-1)-1)*3==18。这个最大面积也是位置0的柱子扩出来的最大矩形面积，在位置0被弹出的时候，这个矩形其实没有找到，但在位置4这里找到了。
3）栈已经空了，过程结束。
9．整个过程结束，所有找到的最大矩形面积中18是最大的，所以返回18。
研究以上9个步骤时我们发现，任何一个位置都仅仅进出栈1次，所以时间复杂度为O(M)。既然每做一次切割处理的时间复杂度为O(M)，一共做N次，那么总的时间复杂度为O(N´M)。
public int maxRecSize(int[][] map) {
if (map == null || map.length == 0 || map[0].length == 0) {
return 0;
}
int maxArea = 0;
int[] height = new int[map[0].length];
for (int i = 0; i < map.length; i++) {
for (int j = 0; j < map[0].length; j++) {
height[j] = map[i][j] == 0 ? 0 : height[j] + 1;
}
maxArea = Math.max(maxRecFromBottom(height), maxArea);
}
return maxArea;
}
public int maxRecFromBottom(int[] height) {
if (height == null || height.length == 0) {
return 0;
}
int maxArea = 0;
Stack<Integer> stack = new Stack<Integer>();
for (int i = 0; i < height.length; i++) {
while (!stack.isEmpty() && height[i] <= height[stack.peek()]) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (i - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
stack.push(i);
}
while (!stack.isEmpty()) {
int j = stack.pop();
int k = stack.isEmpty() ? -1 : stack.peek();
int curArea = (height.length - k - 1) * height[j];
maxArea = Math.max(maxArea, curArea);
}
return maxArea;
}
<p> 本专刊为左程云书《程序员代码面试指南》前三章，已获得官方授权，想看书中更多内容可去购买书籍查看。 同时点击可查看牛客算法笔面试真题精讲班，每周由左老师讲解经典高频校招题目：https://www.nowcoder.com/courses/cover/live/350 本专刊购买后即可解锁所有章节，故不可以退换哦~ </p> <p> <br /> </p>
投递中国移动等公司9个岗位 >
