单调栈结构

#include <bits/stdc++.h>
using namespace std;

int main(){
    int n;
    cin>>n;
    int a[n+1]={-INT_MAX}, l[n+1]={0}, r[n+1]={0}, s[n+1]={0};
    for(int i=1;i<=n;i++)
        scanf("%d", &a[i]);
    for(int i=1,t=0;i<=n;){
        if(a[i]>a[s[t]]){
            l[i] = s[t];
            s[++t] = i++;
        }else
            r[s[t--]] = i;
    }
    for(int i=1;i<=n;i++)
        printf("%d %d\n", l[i]-1, r[i]-1);
    return 0;
}

单调栈，顾名思义，栈中的内容是单调的，我们可以利用这里特性解决一些有趣的问题，如：

水池问题: 给定一组高度，如[0,1,0,2,1,0,1,3,2,1,2,1]，返回可以装的水量6

最大面积问题：给定一组高度如[2,1,5,6,2,3]，返回最大矩形面积10

题目中要求所有值左边👈和右边👉最近的较小值，可以利用单调递增栈：

1. 如果当前元素大于栈顶元素，将元素下标入栈
2. 如果当前元素小于栈顶元素，一一出栈，直到栈顶下标对应元素大于当前元素，然后将当前元素的下标入栈
3. 出栈的过程中，第一个栈顶即为当前元素左边的较小值，剩下的栈顶对应元素的右边较小值为当前元素

遍历完整个数组后，如果栈不为空，一一出栈，此时下标对应的元素无右边较小值，左边较小值为下一个栈顶对应的数组元素。

//
// Created by jt on 2020/8/27.
//
#include <iostream>
#include <vector>
#include <stack>
using namespace std;
 
 
int main() {
    int n;
    cin >> n;
    vector<int> vec;
    for (int i = 0; i < n; ++i) { int a; cin >> a; vec.push_back(a); }
    stack<int> st;  // 单调递增栈
    vector<int> left(n, -1), right(n, -1);  // 分别存储左边较小值和右边较小值的下标
    for (int i = 0; i < n; ++i) {
        while(!st.empty() && vec[i] < vec[st.top()]) {
            int cur = st.top(); st.pop();
            if (!st.empty()) left[cur] = st.top();
            right[cur] = i;
        }
        st.push(i);  // 将当前元素的下标入栈
    }
    while(!st.empty()) {
        int cur = st.top(); st.pop();
        if (!st.empty()) left[cur] = st.top();
    }
    for (int i = 0; i < n; ++i) {
        cout << left[i] << ' ' << right[i] << endl;
    }
}

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);
        }
    }
}

n = int(input())
arr = list(map(int, input().split(' ')))

res = [0]*n
stack = []
for i in range(n):
    while stack and arr[stack[-1]]>arr[i]:
        pop_index = stack.pop()
        if stack:
            left_less_index = stack[-1]
        else:
            left_less_index = -1
        res[pop_index] = [left_less_index, i]
    stack.append(i)
        
while stack:
    pop_index = stack.pop()
    if stack:
        left_less_index = stack[-1]
    else:
        left_less_index = -1
    res[pop_index] = [left_less_index, -1]

for j in res:
    print(str(j[0]) + ' ' + str(j[1]))

function solution(n, nums) {
//   初始化结果数组和单调栈
  const res = new Array(n), stack = []
  let popIndex, leftLessIndex
//   遍历给定的数组
//   因为结果是求数组中每个位置的左右较小的位置，所以单调栈从顶向下应该是递减的
  for (let i = 0; i < n; i++) {
//     违反单调栈的结构时，需要弹出栈顶，并且将当前位置压入
    while (stack.length && nums[stack[stack.length - 1]] > parseInt(nums[i])) {
      popIndex = stack.pop()
      leftLessIndex = stack.length ? stack[stack.length - 1] : -1
      res[popIndex] = [leftLessIndex, i]
    }
    stack.push(i)
  }
//   栈中还有元素，说明即使遍历完数组也没有比栈中剩余的元素小的元素，所以其右边没有比栈中剩余元素小的元素
  while (stack.length) {
    popIndex = stack.pop()
    leftLessIndex = stack.length ? stack[stack.length - 1] : -1
    res[popIndex] = [leftLessIndex, -1]
  }
  return res
}
let n = parseInt(readline())
let nums = readline().split(' ')
let result = solution(n, nums)
for (let i = 0; i < n; i++) {
  print(result[i][0] + ' ' + result[i][1])
}

今天真的去吃了【周末愉快】

let n=parseInt(readline()) 
let line=readline()
let arr=line.split(' ').map(item=>parseInt(item))

let res=Array.from({length:n},()=>[-1,-1])
let stack=[]
for(let i=0;i<n;i++){
    if(stack.length==0){
        stack.push(i)
    }else{

        while(arr[i]<=arr[stack[stack.length-1]]){
            var curIndex=stack.pop()
            res[curIndex][1]=i
        }
        if(stack.length)res[i][0]=stack[stack.length-1]
        stack.push(i)
    }
}
res.forEach(item=>console.log(item.join(' ')))

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
int main()
{
    int n;
    cin>>n;
    int *p_arr = new int[n];
    for(int i = 0;i<n;i++)
    {
        cin>>p_arr[i];
    }
    int (* ans)[2] = new int[n][2];
    stack<int> stacks;
    for(int i = 0;i<n;i++)
    {
        while(!stacks.empty()&&p_arr[stacks.top()] > p_arr[i])
        {
            int cur = stacks.top();
            stacks.pop();
            ans[cur][0] = stacks.empty()? -1 : stacks.top();
            ans[cur][1] = i;
        }
        stacks.push(i);
    }
    while(!stacks.empty())
    {
            int cur = stacks.top();
            stacks.pop();
            ans[cur][0] = stacks.empty()? -1 : stacks.top();
            ans[cur][1] = -1;
    }
    for(int i = 0;i<n;i++)
    {
        cout<<ans[i][0]<<' '<<ans[i][1]<<endl;
    }
}

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

vector<vector<int>> process(const vector<int>& v){
    stack<int> st;
    vector<vector<int>> ans(v.size(), vector<int>(2, 0));
    for(int i = 0; i < v.size(); i++){
        while(!st.empty() && v[st.top()] > v[i]){
            int j = st.top();
            st.pop();
            //L
            ans[j][0] = st.empty() ? -1 : st.top();
            ans[j][1] = i;
        }
        st.push(i);
    }
    while(!st.empty()){
        int j = st.top();
        st.pop();
        //L
        ans[j][0] = st.empty() ? -1 : st.top();
        ans[j][1] = -1;
    }
    return ans;
}

int main(void){
    int n;
    cin >> n;
    vector<int> v(n);
    for(int i = 0; i < n; i++){
        cin >> v[i];
    }
    vector<vector<int>> ans = process(v);
    for(auto a : ans){
        cout << a[0] << " " << a[1] << endl;
    }
    return 0;
}

#include<bits/stdc++.h>
int arr[1000001];
int left[1000001];
int right[1000001];
int main()
{
    int N;
    scanf("%d",&N);
    int x = 0;
    for(int i = 0; i < N; ++i)
    {
        scanf("%d",&x);
        arr[i] = x;
    }
    
    std::stack<int> st;
    for(int i = 0; i < N; ++i)
    {
        while(!st.empty() && arr[st.top()] >= arr[i])
        {
            right[st.top()] = i;
            st.pop();
            
        }
        left[i] = (st.empty() ? -1 : st.top());
        st.push(i);
    }
    
    while(!st.empty())
    {
        right[st.top()] = -1;
        st.pop();
    }
    for(int i = 0; i < N; ++i)
    {
        printf("%d %d\n",left[i],right[i]);
    }
    return 0;
}

#include<iostream>
#include<vector>
#include<stack>
using namespace std;
 
int main() {
    int n;scanf("%d", &n);
    vector<int> a(n);
    for(int i=0;i<n;++i) {
        scanf("%d",&a[i]);
    }
    vector<int>left(n,-1);
    vector<int>right(n,-1);
    stack<int> less;
    for(int i=0;i<n;++i) {
        while(less.size() && a[less.top()] > a[i]) {
            int pre = less.top();less.pop();
            right[pre] = i;
            if(less.size()) left[pre] = less.top();
        }
        less.push(i);
        
    }
    while(less.size()) {
        int x = less.top();less.pop();
        if(less.size()) left[x] = less.top();
    }
    for(int i=0;i<n;++i) {
        cout << left[i]<<' '<<right[i]<<endl;
    }
    return 0;
    
    
}

#include <iostream>
#include <stack>
#include <utility>
using namespace std;
pair<int, int> loc;
pair<int, int> *maxLoc(int arr[], int size){
    pair<int, int> *res = new pair<int, int>[size];
    stack<int> S;
    for(int i = 0; i < size; i++){
        if(S.empty() || arr[S.top()] < arr[i]){
            S.push(i);
        }else{
            while(!S.empty() && arr[S.top()] > arr[i]){
                int temp = S.top();
                S.pop();
                int L = S.empty() ? -1 : S.top();
                res[temp] = make_pair(L,i);
            }
            S.push(i);
        }

    }
    while(!S.empty()){
        int temp = S.top();
        S.pop();
        int L = S.empty() ? -1 : S.top();
        res[temp] = make_pair(L, -1);
    }
    return res;
}

int main()
{
    int n;
    cin >>n;
    int *arr = new int[n];
    for(int i = 0; i < n; i++) cin >> arr[i];
    pair<int, int> *res = maxLoc(arr, n);
    for(int i = 0; i < n; i++)
        cout << res[i].first << " " << res[i].second << endl;
    return 0;
}

import java.util.*;

//第一行输入一个数字 n，表示数组 arr 的长度。
//
//以下一行输出 n个数字，表示数组的值。

//7
//3 4 1 5 6 2 7

//-1 2
//0 2
//-1 -1
//2 5
//3 5
//2 -1
//5 -1
public class Main {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        int  m= sc.nextInt();
        int[] nums=new int[m];
        for (int i = 0; i < m; i++) {
            nums[i]=sc.nextInt();
        }
        Stack<Integer> s=new Stack<>();
        s.push(0);
        int[][] res=new int[m][2];
        res[0][0]=-1;
        int index=1;
        while (index<m){
            int cur=nums[index];//取出当前值
            if(!s.isEmpty()&&cur>nums[s.peek()]){//如果栈不为空，且比栈顶的值大，为了保持单调栈的结构，直接压入栈，后面出栈的时候再设置其左侧和右侧最小就行
                s.push(index);
                index++;
            }else if(s.isEmpty()){//如果栈为空，压入当前的下标
                s.push(index);
                index++;
            }
            else {//栈不为空，且cur<当前的栈顶，这道题数组是不含有重复值的，所以只有大于或者等于
                while (!s.isEmpty()&&cur<nums[s.peek()]){
                    int temp=s.pop();
                    res[temp][1]=index;
                    res[temp][0]= s.isEmpty()?-1:s.peek();
                }
                s.push(index);
                index++;
            }

        }
        while(!s.isEmpty()){//如果有些值本身就比较小，会一直在栈中，所以得设置其值
            int cur=s.pop();
            res[cur][1]=-1;
            res[cur][0]=s.isEmpty()?-1:s.peek();
        }
        res[m-1][1]=-1;//末尾元素的右侧肯定是-1
        for (int i = 0; i < res.length; i++) {
            System.out.printf(String.valueOf(res[i][0])+" ");
            System.out.printf(String.valueOf(res[i][1])+'\n');
        }

    }
}

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]);
        }
    }
}

import java.util.*;
public class PrintMassage{
    public static void PrintIndex(int[] arr,int count){
        int[] A = new int[2];
        for(int i = 0;i < count;i++){
            if(i == 0){
                A[0] = -1;
            }
            if(i == count - 1){
                A[1] = -1;
            }
            int j = i;
            while(j >= 0 && j <= count - 1){
                j -= 1;
                if(j >= 0) {
                    if (arr[i] > arr[j]) {
                        A[0] = j;
                        break;
                    }
                }
                //注意判断没有的情况
                else {
                    A[0] = -1;
                }
            }
            //注意上面的j变化的问题
            j = i;
            while(j >= 0 && j <= count - 1){
                j += 1;
                if(j <= count - 1) {
                    if (arr[i] > arr[j]) {
                        A[1] = j;
                        break;
                    }
                }else {
                    A[1] = -1;
                }
            }
            System.out.println(A[0] + " " + A[1]);
        }
    }
    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();
        }
        PrintIndex(arr,count);
    }
}

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

public class Main {
    /**
     * 没有重复数字时使用单调栈结构，时间复杂度O(N)
     */
    public static int[][] getNearLessNoRepeat(int[] arr) {
        int[][] res = new int[arr.length][2];
        // 排除两种特例：null 空数组[]
        if (arr == null || arr.length < 1) {
            return null;
        }
        // 单调栈初始化
        Stack<Integer> stack = new Stack<>();
        int i = 0;
        int cur;
        while (i < arr.length) {
            if (stack.isEmpty() || arr[i] > arr[stack.peek()]) {
                // 满足从栈顶到栈底单调递减时，压入
                stack.push(i);
                i++;
            } else {
                // 不满足从栈顶到栈底单调递减时，弹出
                cur = stack.pop();
                res[cur][0] = stack.isEmpty() ? -1 : stack.peek();
                res[cur][1] = i;
            }
        }
        // 清算栈中剩余的元素，这些元素右边没有比它小的数字
        while (!stack.isEmpty()) {
            cur = stack.pop();
            res[cur][0] = stack.isEmpty() ? -1 : stack.peek();
            res[cur][1] = -1;
        }
        return res;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.valueOf(bufferedReader.readLine());
        int[] arr = new int[n];
        String[] numbers = bufferedReader.readLine().split(" ");
        for (int i = 0; i < n; i++) {
            arr[i] = Integer.valueOf(numbers[i]);
        }
        int[][] res = getNearLessNoRepeat(arr);
        for (int i = 0; i < res.length; i++) {
            System.out.println(res[i][0] + " " + res[i][1]);
        }
    }
}