在數(shù)組中想找到一個數(shù)，?左邊和右邊比這個數(shù)小、?且離這個數(shù)最近的位置。

?

?

import java.util.ArrayList; import java.util.List; import java.util.Stack;//單調棧 public class MonotonousStack {public static void main(String[] args) {int[] arr = {3,4,2,5,6,0,1};int[][] darr = MonotonousStack.getNearLessNoRepeat(arr);MonotonousStack.printArr(darr);System.out.println("---------------");int[] arr2 = {3,4,2,5,6,0,1};darr = MonotonousStack.getNearLess(arr2);MonotonousStack.printArr(darr);}private static void printArr(int[][] darr){for (int i = 0; i < darr.length; i++) {for (int j = 0; j < darr[0].length; j++) {System.out.print(darr[i][j]+" ");}System.out.println();}}/*** 得到每一個位置上，左邊距離這個數(shù)最近,并且小于當前數(shù)的數(shù)。* 右邊距離這個數(shù)最近,并且小于當前數(shù)的數(shù)。** @param arr(不包含重復數(shù)字)* @return [i][0]左邊, [i][1]右邊*/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++) {while(!stack.isEmpty() && arr[stack.peek()] > arr[i]){// 棧頂?shù)臄?shù)據(jù)比當前位置的數(shù)大,彈出棧頂數(shù)int popIndex = stack.pop();int leftIndex = stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] = leftIndex;res[popIndex][1] = i;}stack.push(i);}while(!stack.isEmpty()){int popIndex = stack.pop();int leftIndex = stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] = leftIndex;res[popIndex][1] = -1;}return res;}/*** 得到每一個位置上，左邊距離這個數(shù)最近,并且小于當前數(shù)的數(shù)。* 右邊距離這個數(shù)最近,并且小于當前數(shù)的數(shù)。** @param arr(包含重復數(shù)字)* @return [i][0]左邊, [i][1]右邊*/public static int[][] getNearLess(int[] arr){int[][] res = new int[arr.length][2];// List<Integer>>放的是位置, 同樣值的東西,位置壓在一起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 leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);for(Integer popi : popIs){res[popi][0] = leftIndex;res[popi][1] = i;}}// 棧頂?shù)闹蹬c當前值相等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 leftIndex = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size()-1);for(Integer popi : popIs){res[popi][0] = leftIndex;res[popi][1] = -1;}}return res;} }

?

總結

以上是生活随笔為你收集整理的常考数据结构与算法:单调栈结构的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內容還不錯，歡迎將生活随笔推薦給好友。