开发网站申请,网站前端和后台,WordPress 有趣插件,辽宁省营商环境建设局网站Problem: 单调栈结构(进阶) 文章目录 思路解题方法复杂度Code 思路 这是一个单调栈的问题。单调栈是一种特殊的栈结构#xff0c;它的特点是栈中的元素保持单调性。在这个问题中#xff0c;我们需要找到每个元素左边和右边第一个比它小的元素。我们可以使用一个单调递减的栈来… Problem: 单调栈结构(进阶) 文章目录 思路解题方法复杂度Code 思路 这是一个单调栈的问题。单调栈是一种特殊的栈结构它的特点是栈中的元素保持单调性。在这个问题中我们需要找到每个元素左边和右边第一个比它小的元素。我们可以使用一个单调递减的栈来解决这个问题。 我们从左到右遍历数组对于每个元素我们将其与栈顶元素进行比较。如果当前元素小于栈顶元素那么我们就找到了栈顶元素右边第一个比它小的元素我们可以将栈顶元素出栈并记录下这个信息。然后我们继续将当前元素与新的栈顶元素进行比较直到当前元素大于栈顶元素或者栈为空然后我们将当前元素入栈。 在遍历结束后栈中可能还会剩下一些元素这些元素右边没有比它们小的元素我们可以将它们出栈并记录下这个信息。 最后我们需要处理一下相等的情况。如果一个元素右边第一个比它小的元素和它相等那么我们需要找到右边第一个不等于它的元素。 解题方法 我们使用一个栈和一个二维数组来解决这个问题。栈用来存储元素的索引二维数组用来存储每个元素左边和右边第一个比它小的元素的索引。 复杂度
时间复杂度: O ( n ) O(n) O(n)我们只需要遍历一次数组。 空间复杂度: O ( n ) O(n) O(n)我们需要一个栈和一个二维数组来存储信息。 Code
import java.util.*;
import java.io.*;// 注意类名必须为 Main, 不要有任何 package xxx 信息
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 1000010;static int n, r;static int[] stack new int[MAXN];static int[][] ans new int[MAXN][2];static int[] arr 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) {out.println(ans[i][0] ans[i][1]);}out.flush();}private static void deal() {r 0;int cur;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;}
}
