单调栈结构
此贴为笔者学习左神算法的记录。
【题目】 给定一个不含有重复值的数组 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(N2)的解是非常容易的，每个位置分别向左和向右遍历一下，总可以确定。本书不再详述，具体过程请看如下的 rightWay 方法。
O(N^2)算法
解法一：
public class RightWay {
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;
}
}
解法二：
public class MyRightWay {
public int[][] getRightWay(int[] arr) {
int[][] res = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) { // O(N)
res[i][0] = getLeftOne(arr, i); // 两个操作加起来O(N)
res[i][1] = getRightOne(arr, i);
}
return res;
}
public int getLeftOne(int[] arr, int i) {
for (int j = i - 1; j >= 0; j--) {
if (arr[j] < arr[i]) {
return j;
}
}
return -1;
}
public int getRightOne(int[] arr, int i) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[i]) {
return j;
}
}
return -1;
}
public static void main(String[] args) {
MyRightWay myRightWay = new MyRightWay();
int[] arr = new int[] {3, 4, 1, 5, 6, 2, 7};
int[][] res = myRightWay.getRightWay(arr);
for (int[] curArr : res) {
for (int cur : curArr) {
System.out.print(cur + " ");
}
System.out.println();
}
}
}
关键在于生成所有位置的相应信息，时间复杂度做到 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 位置。 证明完毕。整个流程中，每个位置都进栈一次、出栈一次，所以整个流程的时间复杂度就是 O(N)，请看如下的 getNearLessNoRepeat 方法。
public class GetNearLessNoRepeat {
public static int[][] getNearLessNoRepeat(int[] arr) {
/**
* 申请一个栈空间，用于存放数组元素的下标，栈中元素所指代的值从栈顶到栈底是递减结构
*/
Stack<Integer> stack = new Stack<>();
// 申请一个二维数组，存放结果
int[][] res = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) {
/**
* 栈不为空，且栈顶元素所指代的值大于当前元素arr[i]，那么当前元素不能放入栈中，会破坏递减结构
* 就需要将栈中元素逐一弹出，然后逐一比对
* 当前栈中弹出的元素的下一个元素是当前元素左边距离当前元素最近且小于当前元素的那个元素
* 当前遍历到的元素arr[i]是当前栈中弹出元素右边距离当前元素最近的那个元素
*/
while (!stack.isEmpty() && arr[stack.peek()] > arr[i]) {
Integer popIndex = stack.pop();
// 该元素弹出后，如果栈中没有元素就代表当前弹出元素左边没有这个元素小的元素
res[popIndex][0] = stack.isEmpty() ? -1 : stack.peek();
res[popIndex][1] = i;
}
// 栈结构调整完，再将新元素压入就不会改变栈的递减结构
stack.push(i);
}
// 把栈中元素弹出
while(!stack.isEmpty()) {
Integer popIndex = stack.pop();
// 左边最近的比弹出元素小的元素在该元素下方
res[popIndex][0] = stack.isEmpty() ? -1 : stack.peek();
// 该元素右边没有比这个元素小的元素
res[popIndex][1] = -1;
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[] {1, 3, 4, 6, 2, 5, 7, 9};
int[][] res = getNearLessNoRepeat(arr);
for (int[] curArr : res) {
for (int cur : curArr) {
System.out.print(cur + " ");
}
System.out.println();
}
}
}
进阶问题，可能含有重复值的数组如何使用单调栈。其实整个过程和原问题的解法差不多。举个例子来说明，初始时 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}。 全部过程请看如下代码中的 getNearLess 方法。
public class GetNearLess {
public static int[][] getNearLess(int[] arr) {
Stack<List<Integer>> stack = new Stack<>();
int[][] res = new int[arr.length][2];
for (int i = 0; i < arr.length; i++) {
while (!stack.isEmpty() && arr[stack.peek().get(0)] > arr[i]) {
List<Integer> popLs = stack.pop();
// 取出栈顶元素中最晚加入列表的那个，因为那个元素离当前元素最近
int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer cur : popLs) {
res[cur][0] = leftIndex;
res[cur][1] = i;
}
}
if (!stack.isEmpty() && arr[stack.peek().get(0)] == arr[i]) {
// 如果栈不为空，且栈顶那个列表中元素所代表的值等于arr[i]，就将i加入到这个列表中
stack.peek().add(Integer.valueOf(i));
} else {
// 上述条件不成立，则新建一个列表压入栈中
List<Integer> list = new ArrayList<>();
list.add(i);
stack.push(list);
}
}
// 清算栈中剩下的元素
while (!stack.isEmpty()) {
List<Integer> popLs = stack.pop();
int leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);
for (Integer cur : popLs) {
res[cur][0] = leftIndex;
res[cur][1] = -1;
}
}
return res;
}
public static void main(String[] args) {
int[] arr = new int[] {3, 2, 4, 5, 2, 3, 1, 8, 2};
int[][] res = getNearLess(arr);
for (int[] curArr : res) {
for (int cur : curArr) {
System.out.print(cur + " ");
}
System.out.println();
}
}
}
#单调栈结构#笔者学习数据结构与算法的心得与经验。
腾讯公司福利 448人发布
投递传音控股等公司10个岗位 >