830. 单调栈

Problem: 830. 单调栈

思路

这是一个单调栈的问题。单调栈是一种特殊的栈结构，它的特点是栈中的元素保持单调性。在这个问题中，我们需要找到每个元素左边第一个比它小的元素，这就需要使用到单调递增栈。

我们从左到右遍历数组，对于每个元素，如果栈为空或者当前元素大于栈顶元素，就将当前元素入栈；否则，就将栈顶元素出栈，直到栈为空或者找到一个栈顶元素小于当前元素，然后将当前元素入栈。这样，栈中的元素就始终保持了单调递增的性质。

在这个过程中，每当我们要将一个元素出栈时，就找到了这个元素左边第一个比它小的元素（就是当前的栈顶元素）。我们可以在这个时候记录下这个信息。

解题方法

我们使用一个栈和一个二维数组。栈用来存储元素的索引，二维数组用来存储每个元素左边第一个比它小的元素的索引和右边第一个比它小的元素的索引。

在遍历数组的过程中，我们使用一个指针r来表示栈顶。每当我们要将一个元素i入栈时，如果栈不为空并且栈顶元素大于等于当前元素，就将栈顶元素出栈，并记录下这个元素左边第一个比它小的元素的索引（就是当前的栈顶元素）和右边第一个比它小的元素的索引（就是当前的元素i）。然后将元素i入栈。

在遍历完数组后，栈中可能还有元素。这些元素右边没有比它小的元素，所以我们将这些元素出栈，并记录下这个元素左边第一个比它小的元素的索引（就是当前的栈顶元素）。

最后，我们需要修正一下结果。因为可能存在连续的相同的元素，这些元素右边第一个比它小的元素应该是相同的。所以我们从右到左遍历数组，如果一个元素和它右边的元素相同，就将它的右边第一个比它小的元素的索引更新为它右边的元素的右边第一个比它小的元素的索引。

复杂度

时间复杂度:

$O(n)$，我们只遍历了一次数组。

空间复杂度:

$O(n)$，我们使用了一个栈和一个二维数组来存储信息。

Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.io.StreamTokenizer;public class Main {static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));static StreamTokenizer sr = new StreamTokenizer(in);static int MAXN = (int) (1e5 + 10);static int n, r;static int[] arr = new int[MAXN];static int[][] ans = new int[MAXN][2];static int[] stack = new int[MAXN];public static void main(String[] args) throws IOException {n = nextInt();for (int i = 0; i < n; i++) {arr[i] = nextInt();}// 找出左边第一个比自己小的元素deal();for (int i = 0; i < n; i++) {if (ans[i][0] != -1) {out.print(arr[ans[i][0]] + " ");} else {out.print(-1 + " ");}}out.flush();}private static void deal() {// TODO Auto-generated method stubint cur;r = 0;// 计算阶段for (int i = 0; i < n; i++) {while (r > 0 && arr[stack[r - 1]] >= arr[i]) {cur = stack[--r];ans[cur][0] = r > 0 ? stack[r - 1] : -1;ans[cur][1] = i;}stack[r++] = i;}// 清算阶段while (r > 0) {cur = stack[--r];ans[cur][0] = r > 0 ? stack[r - 1] : -1;ans[cur][1] = -1;}// 修正阶段for (int i = n - 2; i >= 0; i--) {if (ans[i][1] != -1 && arr[ans[i][1]] == arr[i]) {ans[i][1] = ans[ans[i][1]][1];}}}static int nextInt() throws IOException {sr.nextToken();return (int) sr.nval;}}