[程序员代码面试指南]栈和队列-单调栈结构(单调栈)

问题描述

给定一个数组，找到每一个位置左边和右边离它最近的且值比它小的位置，返回一个二维数组表示每个位置对应的两个位置。

解题思路

• 使用单调栈，保证栈内元素从栈顶到栈底严格单调递减。
• 每个元素入出栈一次，时间复杂度O（n）
  具体的，如果x位置被弹出，在栈中位于ta下面的位置的元素就是满足题意的左边元素，当前元素就是满足题意的右边元素。
  若该位置下面无元素，则左边为-1.
  遍历阶段结束后，清算栈中剩下位置，所有此阶段弹出的右边为-1.、

todo

处理含重复元素数组的改进方法待做。

代码

import java.util.Stack;

public class Main {
	public static void main(String args[]) {
		int[] arr= {3,4,1,5,6,2,7};
		//int[] arr= {3,1,3,4,3,5,3,2,2};
		int[][] nearPos=nearSmallerNumPos(arr);
		for(int i=0;i<nearPos.length;++i) {
			for(int j=0;j<nearPos[0].length;++j) {
				System.out.print(nearPos[i][j]);
			}
			System.out.print("
");
		}
	}
	public static int[][] nearSmallerNumPos(int arr[]){
		int[][] nearPos=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 pos=stack.pop();
				nearPos[pos][0]=stack.isEmpty()?-1:stack.peek();
				nearPos[pos][1]=i;//
			}
			stack.push(i);//
		}
		while(!stack.isEmpty()) {
			int pos=stack.pop();//
			nearPos[pos][0]=stack.isEmpty()?-1:stack.peek();
			nearPos[pos][1]=-1;
		}
		return nearPos;
	}
}