题目
给定一个不含重复值的数组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)
思路
关键在于生成所有的位置相应信息，时间复杂度做到O(N)，这需要使用到单调栈结构。
原问题：准备一个栈，记为stack<Integer> ,栈中放入的元素是数组的位置，开始时stack为空，如果找到每一个 i 位置左边和右边离 i 位置最近且值比arr[i]小的位置，那么需要让stack从栈顶到栈底的位置所有代表的值是严格递减；找到每一个位置 i 位置的左边和者右边离 i 最近且值比arr[i]大的位置，那么需要让stack从栈顶到栈底的位置所代表的值是严格增的。
下面用例子来展示单调栈的使用和求解流程，初始时arr={3,4,1,5,6,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={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位置，不会破坏tack从栈顶到栈低的位置所代表的值是严格递减的，那么直接放入，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}；
至此，已经全部生成了每个位置的信息。全过程查看getNearLessNoRepear()方法下面证明在单调栈中，如果 x 位置被弹出，在栈中位于 x 位置下面的位置为什么就是 x 位置左边离 x 位置最近且值比arr[x]小的位置；当前遍历到的位置就是 x 位置右边离 x 位置最近且值比arr[x]小的位置。假设 stack当前栈顶位置是x，值是5；x下面是 i 位置，值是1；当前遍历到 j 位置，值是4.如图下图所示，请注意整个数组中是没有重复值的。
示意图
当前来到 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的数，那么位置 (值是1) 会被提前弹出，在栈中 i 位置和 x 位置就不可能贴在一起。如果在1和5之间存在大于1但小于5的数，那么在栈中 i 位置和 x 位置之间一定会夹上一个别的位置，也不可能贴在一起，所以1和5之同的数要么没有，要么一定比5大，那么 x 位置左边离 x 位置最近且小于arr[x] 的位置就是 i 位置
证明完毕。进阶问题，可能含有重复值的数组如何使用单调栈。
其实整个过程和原问题的解法差不多，举个例子来说明，初始时arr={3,1,3,4,3,5,3,2,2}， stack从栈顶到栈底为：{}
遍历到arr[0]==3，发现stack为空，就直接放入0位置，stak从栈顶到栈底为:{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[3]={1,7}，ans[4]={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}；
全过程查看getNearLess()方法
代码演示
package com.itz.zcy.stackAndQueue;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;
/**
* 给定一个不含重复值的数组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……
* <p>
* 进阶问题：给定一个可能含有重复的数组arr，找到一个 i 位置左边和右边离 i 最近且值比arr[i]小的位置。返回所有位置的相应信息。
*/
public class MonotonousStack {
/**
* 采用的是原始的暴力解法，该方法的时间复杂度是O(N^2)
*
* @param arr 需要操作的数组
* @return
*/
public static 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;
// 向i位置左边寻找最近最小的
while (cur >= 0) {
if (arr[cur] < arr[i]) {
leftLessIndex = cur;
break;
}
cur--;
}
cur = i + 1;
// 向i位置右边寻找最近最小的
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)。对数组的遍历也是只有一次
* 在这个过程中分为两个阶段，在这个遍历阶段对数组进行遍历，然后把能找的的都存入数组中把右边能找都左边找不到也存入了，
* 清算阶段把，把左边能找到，右边找不到的和最小的存入。
* @param arr 需要操作的数组
* @return
*/
public static int[][] getNearLessNoRepeat(int[] arr) {
int[][] res = new int[arr.length][2];
// 定义一个临时栈
Stack<Integer> stack = new Stack<>();
// 遍历阶段
for (int i = 0; i < arr.length; i++) {
// 判断但放入的时候后 stack从栈顶到栈底不是单调递减的
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
int popIndex = stack.pop();
// 当栈为空的时候 表示下面没有了是-1
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数组中存在重复的元素
* 方法和没有重复的差不多，只是用List来做节点存入stack中，多引入一种数据结构
* 在遇见重复的选最晚的加入
* @param arr
* @return
*/
public static 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.add(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;
}
public static void main(String[] args) {
int[] arr = {3, 4, 1, 5, 6, 2, 7};
int[] a = {3,1,3,4,3,5,3,2,2};
System.out.println(Arrays.deepToString(getNearLessNoRepeat(arr)));
System.out.println(Arrays.deepToString(rightWay(arr)));
System.out.println(Arrays.deepToString(getNearLess(arr)));
System.out.println(Arrays.deepToString(getNearLess(a)));
// [[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]]
// [[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]]
// [[-1, 2], [0, 2], [-1, -1], [2, 5], [3, 5], [2, -1], [5, -1]]
// [[-1, 1], [-1, -1], [1, 7], [2, 4], [1, 7], [4, 6], [1, 7], [1, -1], [1, -1]]
}
}
总结
在方法一用最原始的方法使用暴力的方法对时间复杂度是O(N^2)，在方法二中使用了单调栈的数据结构，arr数组和进栈出栈都只做了一次所以时间复杂度是O(N)。进阶问题大致的思路和其他差不多，就是多引入了一种数据结构，引入了Lis来存储元素，对于重复的元素就解决了，但是他们的时间复杂度还是O(N)
文献：左程云著 《程序员代码面试指南IT名企算法与数据结构题目最优解》（第二版）
版权声明：此文版权归作者所有！
