单调栈结构

牛客测试链接

问题描述

给定一个可能含有重复值的数组 arr，找到每一个 i 位置左边和右边离 i 位置最近且值比 arr[i] 小的位置。返回所有位置相应的信息。

解题思路

我们可以使用单调栈来解决这个问题。单调栈是指栈中的元素保持单调递增或单调递减的栈结构。

具体的解题思路如下：

1. 创建一个栈 stack 和一个二维数组 ans，用于存储结果。
2. 遍历数组 arr，对于每个元素 arr[i]，执行以下操作：
   • 如果栈不为空且栈顶元素 arr[stack[top]] 大于等于 arr[i]，则弹出栈顶元素，将其左边和右边离 i 位置最近且值比 arr[i] 小的位置记录到 ans 中。
   • 将 i 入栈。
3. 遍历结束后，如果栈不为空，则将栈中剩余的元素弹出，并将其左边离 i 位置最近且值比 arr[i] 小的位置记录到 ans 中。
4. 修正 ans 中的结果，对于相同值的元素，将其右边离 i 位置最近且值比 arr[i] 小的位置修正为 ans[ans[i][1]][1]。
5. 返回 ans。

代码实现

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 {
    public static int MAXN = 1000001;

    public static int[] arr = new int[MAXN];

    public static int[] stack = new int[MAXN];

    public static int[][] ans = new int[MAXN][2];

    public static int n, r;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StreamTokenizer in = new StreamTokenizer(br);
        PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
        while (in.nextToken() != StreamTokenizer.TT_EOF) {
            n = (int) in.nval;
            for (int i = 0; i < n; i++) {
                in.nextToken();
                arr[i] = (int) in.nval;
            }
            compute();
            for (int i = 0; i < n; i++) {
                out.println(ans[i][0] + " " + ans[i][1]);
            }
        }
        out.flush();
        out.close();
        br.close();
    }

    static void compute() {
        int 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];
            }
        }
    }
}

以上是使用 Java 实现的解题代码。

总结

本题通过使用单调栈结构，可以高效地找到每一个位置左边和右边离该位置最近且值比该位置小的位置。通过遍历数组并利用栈的特性，可以在 O(n) 的时间复杂度内解决该问题。