单调栈结构

[编程题]单调栈结构

热度指数：3663 时间限制：C/C++ 4秒，其他语言8秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

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

输入描述:

第一行输入一个数字 n，表示数组 arr 的长度。

以下一行输出 n个数字，表示数组的值。

输出描述:

输出n行，每行两个数字 L 和 R，如果不存在，则值为-1，下标从0开始。

示例1

输入

7
3 4 1 5 6 2 7

输出

备注:

算法知识视频讲解

Java

pein531

单调栈的应用

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.Stack;

public class Main {
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        String[] strArr = br.readLine().split(" ");
        int[] arr = new int[n];
        int[][] res = new int[n][2];       // res[i]分别表示arr[i]左边和右边离它最近且比它小的数
        for(int i = 0; i < n; i++){
            res[i][0] = -1;
            res[i][1] = -1;
        }
        Stack<Integer> stack = new Stack<>();
        for(int i = 0; i < n; i++){
            arr[i] = Integer.parseInt(strArr[i]);
            if(stack.isEmpty()){
                stack.push(i);
            }else{
                if(arr[stack.peek()] < arr[i]){
                    // 单调性保持，压栈
                    stack.push(i);
                }else{
                    // 单调性被破坏，弹栈
                    while(!stack.isEmpty() && arr[stack.peek()] > arr[i]){
                        int temp = stack.pop();
                        res[temp][1] = i;      // 栈中所有右边比它小的元素都是arr[i]
                        if(!stack.isEmpty()) res[temp][0] = stack.peek();     // arr[temp]左边是temp下边压着的数
                        else res[temp][0] = -1;
                    }
                    if(stack.isEmpty()) res[i][0] = -1;
                    else res[i][0] = stack.peek();
                    stack.push(i);
                }
            }
        }
        // 清算阶段
        while(!stack.isEmpty()){
            int temp = stack.pop();
            if(!stack.isEmpty()) res[temp][0] = stack.peek();
            else res[temp][0] = -1;
        }
        for(int i = 0; i < n; i++) System.out.println(res[i][0] + " " + res[i][1]);
    }
}

发表于 2021-11-18 13:20:52 回复(1)

Java

D沧笙踏歌

import java.util.Scanner;
import java.util.Stack;
 
public class Main {
 
    private int[][] minIndex;
    private int[] arr;
 
    Main(int[] arr){
        this.arr = arr;
        int n = arr.length;
        minIndex = new int[n][2];
        for (int i=0; i<n; i++){
            minIndex[i][0] = -1;
            minIndex[i][1] = -1;
        }
    }
 
    public int[][] findMinIndex(){
        Stack<Integer> stack = new Stack<>();
        for (int i=0; i < arr.length; i++){
            int cur = arr[i];
            if (stack.isEmpty()){
                stack.push(i);
            }else {
                if (cur > arr[stack.peek()]){
                    minIndex[i][0] = stack.peek();
                }else {//cur < stack.peek()
                    while (!stack.isEmpty() && arr[stack.peek()] > cur) {
                        minIndex[stack.pop()][1] = i;
                    }
                    if (!stack.isEmpty()){
                        minIndex[i][0] = stack.peek();
                    }
                }
                stack.push(i);
            }
        }
        return minIndex;
    }
 
    public static void main(String[] args) {
 
        Scanner sc = new Scanner(System.in);
        int count = sc.nextInt();
        int[] arr = new int[count];
        for(int i = 0;i < count;i++){
            arr[i] = sc.nextInt();
        }
 
        Main singleStack = new Main(arr);
        int[][] minIndex = singleStack.findMinIndex();
        for (int i=0; i<arr.length; i++){
            System.out.println(minIndex[i][0]+" "+minIndex[i][1]);
        }
    }
}

发表于 2020-08-03 17:56:52 回复(0)

Java

deh

import java.util.Scanner;
import java.util.Stack;

public class Main {

    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]) {
                int popIndex = stack.pop();
                int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
                res[popIndex][0] = leftLessIndex;
                res[popIndex][1] = i;
            }
            // 否则当前遍历到的数组的值大，压入不会破坏stack从栈顶到栈底递减的顺序
            stack.push(i);
        }
        // 遍历结束，清算栈中剩下的位置，因为没有当前遍历到的位置，右边位置一律为-1
        while (!stack.isEmpty()) {
            int popIndex = stack.pop();
            int leftLessIndex = stack.isEmpty() ? -1 : stack.peek();
            res[popIndex][0] = leftLessIndex;
            res[popIndex][1] = -1;
        }
        return res;
    }

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNextInt()) {
            int n = sc.nextInt();
            int[] data = new int[n];
            for (int i = 0; i < data.length; i++) {
                data[i] = sc.nextInt();
            }
            int[][] result = getNearLessNoRepeat(data);
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < result.length; i++) {
                sb.append(result[i][0]).append(" ").append(result[i][1]).append('\n');
            }
            System.out.print(sb);
        }
    }
}

发表于 2020-04-05 19:14:35 回复(0)