首页 > 试题广场 >

单调栈结构

[编程题]单调栈结构
  • 热度指数:3559 时间限制: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

输出

-1 2
0 2
-1 -1
2 5
3 5
2 -1
5 -1

备注:

单调栈的应用
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 回复(0)
#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;
}

发表于 2020-04-20 00:46:16 回复(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;
    }
}
发表于 2020-08-27 11:07:05 回复(0)
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)
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]))
发表于 2021-11-09 23:28:10 回复(0)
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])
}

发表于 2021-08-30 11:05:31 回复(0)

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

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(' ')))
编辑于 2021-06-25 17:36:43 回复(0)
#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;
    }
}

发表于 2021-06-08 20:30:27 回复(0)
#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;
}
本题主要在于使用栈来维护,考虑到数组为非重复元素
但遇到一个写错的地方是:v[st.top()] < v[i]
发表于 2021-05-28 15:57:33 回复(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;
}

发表于 2021-02-20 10:21:31 回复(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;
    
    
}








发表于 2021-02-02 19:32:22 回复(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;
}
发表于 2021-02-01 20:39:57 回复(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');
        }

    }
}

发表于 2020-09-11 11:22:40 回复(0)
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)
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);
    }
}

发表于 2020-04-26 19:33:42 回复(0)
Brute-force方法不难想,遍历所有元素,左右两侧找min值,O(n^2)。那么典型的改进做法是时间换空间,需要一个辅助栈(储存索引),自底向顶是递增分布,算法时间复杂度即可降为O(n)。
程序逻辑如下:遍历到元素i,值为arr[i],与栈顶元素的值arr[stk.top()]做比较,1)若小于则元素i即为栈顶右侧最小的元素,栈的有序性决定左侧最小为栈顶的第二元素(空则为-1);2)若大于则继续进行入栈操作。
最后对栈中剩余元素依次pop出,右侧均为-1(此时右侧不存在小于该元素值的元素)。上C++代码:
#include <bits/stdc++.h>

using namespace std;

int main(){
    int n;
    cin >> n;
    int arr[n];
    for(int i=0; i<n; i++)
        cin >> arr[i];
    pair<int, int> help_vec[n];
    
    stack<int> stk;
    for(int i=0; i<n; i++){
        while(!stk.empty() && arr[i]<arr[stk.top()]){
            int top = stk.top();
            stk.pop();
            help_vec[top].first = (stk.empty()) ? -1 : stk.top();
            help_vec[top].second = i;
        }
        stk.push(i);
    }
    while(!stk.empty()){
        int top = stk.top();
        stk.pop();
        help_vec[top].first = (stk.empty()) ? -1: stk.top();
        help_vec[top].second = -1;
    }
    
    // output
    for(int i=0; i<n; i++){
        cout<< help_vec[i].first << ' ' << help_vec[i].second << endl;
    }
    return 0;
}


发表于 2020-02-14 21:10:00 回复(0)
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]);
        }
    }
}

发表于 2019-12-15 16:11:56 回复(0)