0%

单调栈结构

发表于 更新于 分类于
本文字数： 阅读时长 ≈

题目：给定一个数组(不含重复值)，找到每一个位置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可能有重复值，找到每个位置i左边和右边的离i最近的且比arr[i]小的位置。

要求：arr长度为n，实现原问题和进阶问题的解法，时间复杂度为O(N)。

先看暴力解法，思路较简单，T(n) = O(n*n),每个位置分别向左和向右遍历一下，总可以确定。代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
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;
			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][0] = rightLessIndex;
		}
		return res;
}

单调栈结构解决原问题：

  • 1，准备一个栈，记为stack,栈中放数组的位置，开始stack为空，如果找到每一个i位置左边和右边离i位置最近的且比arr[i]小的位置，那么需要让stack从栈顶到栈底的位置所代表的值是严格递减的；如果找到每一个i位置左边和右边离i位置最近且值比arr[i]大的位置，那么需要让stack从栈顶到栈底的位置所代表的值是严格递增的。我们讨论前者，实际上这两种情况原理一样。

下面举例说明这个问题：初始时arr={3,4,1,5,6,2,7};stack从栈顶到栈底为{}(意思是为空)。

  • 1，遍历到arr[0] = 3，stack为空，直接放入0位置。stack从栈顶到栈底为{0位置(值为3)};
  • 2，遍历到arr[1] = 4，发现直接放入1位置不会破坏stack要求的特性，直接放入1位置。stack从栈顶到栈底为{1位置(值是4)、0位置(值为3)};
  • 2，遍历到arr[2] = 1，发现直接放入2位置会破坏stack要求的特性，从stack开始弹出位置，如果x位置被弹出，在栈中位于x下面的的位置，就是x位置左边离x位置最近且比arr[x]小的位置；当前遍历到的位置就是x位置右边离x位置最近且比arr[x]小的位置。从stack中弹出1，在栈中位于1位置下面的是位置0，当前遍历到的位置是2，所以ans[1] = {0,2}。弹出1位置后，发现放入2位置(值是1)还会破坏规则，所以继续弹出位置，这次弹出位置0。在栈中位于位置0下面已经没有位置了，说明在位置0左边不存在比arr[0]小的值，当前遍历到的位置是位置2，所以ans[0] = {-1,2}。stack已经为空，所以放入2位置(值为1)，stack从栈顶到栈底为：{2位置{值是1}};….

以此类推，得到ans[4] = {3,5},ans[3] = {2,5},ans[6] = {5,-1},ans[5] = {2,-1},ans[2] = {-1,-1}。

简单证明单调栈中，如果x位置被弹出，在栈中位于x位置下面的位置为什么就是x位置左边离x位置最近且比arr[x]小的位置

  • 答：如果x位置被弹出，在栈中位于x位置下面的位置为什么就是x位置左边离x位置最近且值比arr[x]小的位置；当前遍历到的位置就是x位置右边离x位置最近且比arr[x]小的位置。假设stack当前栈顶位置是x，值是5；x下面是i位置，值是1；当前遍历到j位置，值是4。整个栈是没有重复值的。当前遍历到j位置，但是x位置已经在栈中，所以x位置肯定在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和5之间存在小于1的数，那么i位置(值为1)会被提前弹出，在栈中i位置和x位置就不可能贴在一起，如果在1和5之间存在大于1但小于5的数，那么在栈中i位置和x位置之间一定会夹上一个别的位置，也不可能贴在一起，所以1和5之间的数要么没有，要么一定大于5，那么x位置左边离x位置最近且小于arr[x]的位置就是i位置。

证明结束，整个流程中，每个位置都进栈一次、出栈一次，所以整个流程的时间复杂度是O(n)，看如下的getNearLessNoRepeat方法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
	public int[][] getNearLessNoRepeat(int[] arr) {
		int[][] res = new int[arr.length][2];
		Stack<Integer> stack = new Stack<Integer>();
		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;
	}
}

进阶问题，可能含有重复的数组使用单调栈，其实过程和原问题的解法差不多。全过程看如下代码：

1
2