本題來自左神《程序員面試代碼指南》“單調(diào)棧結(jié)構(gòu)”題目。

題目

給定一個不含有重復(fù)值的數(shù)組 arr，找到每一個 i 位置左邊和右邊離 i 位置最近且值比 arr[i] 小的位置。返回所有位置相應(yīng)的信息。

舉例

輸入：

arr = {3, 4, 1, 5, 6, 2, 7}

返回如下二維數(shù)組作為結(jié)果：

{{-1, 2}, // -1表示不存在，整體含義為：arr[0]左邊離arr[0]最近且比arr[0]小的是arr[-1]，// arr[0]右邊離arr[0]最近且比arr[0]小的是arr[2]，{ 0, 2},{-1, -1},{ 2, 5},{ 3, 5},{ 2, -1},{ 5, -1}, }

題解

本題實現(xiàn)時間復(fù)雜度為 O(n^2) 的解是非常容易的，每個位置分別向左和向右遍歷一下即可，本文不再詳述。

若要想時間復(fù)雜度達到 O(n)，需要用到單調(diào)棧結(jié)構(gòu)。

下面我們詳細講解單調(diào)棧結(jié)構(gòu)。

1、原問題：無重復(fù)元素的單調(diào)棧

思路總結(jié)：每一次從 棧頂 將 大于 當(dāng)前元素的彈出



（過程草稿）

代碼：

// O(n)，無重復(fù)元素的單調(diào)棧 public static int[][] getNearLessNoRepeat(int[] arr) {int[][] res = new int[arr.length][2];Stack<Integer> stack = new Stack<>(); // 單調(diào)棧for (int i = 0; i < arr.length; i++) {while (!stack.isEmpty() && arr[i] < stack.peek()) { // 若當(dāng)前位置元素[小于]棧頂位置元素，則一直彈出棧頂元素，直到不小于為止int popIndex = stack.pop();int leftLessIndex = stack.isEmpty() ? -1 : stack.peek(); // 棧中當(dāng)前元素上方的元素res[popIndex][0] = leftLessIndex; // 記錄彈出元素[左邊]，[第一個小于彈出元素的元素]的下標(biāo)res[popIndex][1] = i; // 記錄彈出元素[右邊]，[第一個小于彈出元素的元素]的下標(biāo)}stack.push(i); // 當(dāng)前元素入棧}// 遍歷完成，對棧中剩余元素進行清算while (!stack.isEmpty()) {int popIndex = stack.pop();int leftIndex = stack.isEmpty() ? -1 : stack.peek();res[popIndex][0] = leftIndex;res[popIndex][1] = -1;}return res; }

2、進階問題：含有重復(fù)元素的單調(diào)棧

其實整個過程和原問題的解法差不多。只不過是將重復(fù)的元素壓在一起，并看作一個整體進行彈出。


(過程草稿）

代碼：

import java.util.*;//單調(diào)棧結(jié)構(gòu) public class Main {public static int[][] getNearLess(int[] arr) {int[][] res = new int[arr.length][2];ArrayDeque<List<Integer>> stack = new ArrayDeque<>();for (int i = 0; i < arr.length; i++) {while (!stack.isEmpty() && arr[i] < arr[stack.peek().get(0)]) {List<Integer> topList = stack.pop();int leftLessIdx = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer n : topList) {res[n][0] = leftLessIdx;res[n][1] = i;}}if (!stack.isEmpty() && arr[i] == arr[stack.peek().get(0)]) {stack.peek().add(i);} else {List<Integer> list = new ArrayList<>();list.add(i);stack.push(list);}}while (!stack.isEmpty()) {List<Integer> topList = stack.pop();int leftLessIdx = stack.isEmpty() ? -1 : stack.peek().get(stack.peek().size() - 1);for (Integer n : topList) {res[n][0] = leftLessIdx;res[n][1] = -1;}}return res;}public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = sc.nextInt(); // 元素總個數(shù)int[] arr = new int[n];for (int i = 0; i < n; i++) {arr[i] = sc.nextInt();}int[][] res = getNearLess(arr);for (int i = 0; i < n; i++) {System.out.println(res[i][0] + " " + res[i][1]);}} }

輸入：

9 3 1 3 4 3 5 3 2 2

輸出：

-1 1 -1 -1 1 7 2 4 1 7 4 6 1 7 1 -1 1 -1

參考

• 單調(diào)棧結(jié)構(gòu) - CSDN博客
• 單調(diào)棧結(jié)構(gòu) TIAN_HE - CSDN博客

總結(jié)

以上是生活随笔為你收集整理的左神算法：单调栈结构（Java版）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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