洛谷(2947)向右看齐-单调栈-链表

简介: 单调栈对新手来说不好理解,但链表就特别简单,但在有时间限制的竞赛中,很容易超时,因此如果实在要使用链表,注意使用链表的类型,Java提供的两种实现链表的方式

前言

单调栈对新手来说不好理解,但链表就特别简单,但在有时间限制的竞赛中,很容易超时,因此如果实在要使用链表,注意使用链表的类型,Java提供的两种实现链表的方式:


LinkedList 适用于大量增删的操作,这道题不适合

ArrayList 适用于大量遍历搜索的操作,这道题因为需要一直搜索遍历链表直到找到比自己大的结点,所以更适用!

二者时间区别见下图:

LinkedList:

image.png

ArrayList:

image.png

但能理解单调栈最好了:

image.png

单调栈实现

import java.util.*;

import java.util.Stack;

public class Main{
    public static void main(String args[]){
        //数据准备
        Deque<Integer> stack = new ArrayDeque<>();
        Scanner input = new Scanner(System.in);
        int[] cows = new int[100100];
        int n = input.nextInt();    //n头牛
        for(int i=1;i<=n;i++){
            int height = input.nextInt();
            cows[i] = height;
        }
        //算法部分
        int[] res=new int[100100];
        for(int i=n;i>=1;i--){
            while(!stack.isEmpty() && cows[stack.peek()]<=cows[i]){
                stack.pop();
            }
            if(stack.isEmpty()){
                res[i] = 0;
            }else{
                res[i] = stack.peek();
            }
            stack.push(i);
        }
        for(int i=1;i<=n;i++){
            System.out.println(res[i]);
        }
    }
}



链表实现

遍历的思想像选择排序,他也是把第i(初始化是1)个节点挨个和第 j(初始化为i+1,j初始化值始终为i的下一个节点值,即i+1)个节点比较,然后 j++;

l
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;
//用链表实现 奶牛向右看齐的问题
public class example1_6 {
    public static void main(String[] args) {
        ArrayList<Integer> link = new ArrayList<>();
        link.add(0);//头节点
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        for (int i = 0; i < n; i++) {
            int height = input.nextInt();
            link.add(height);   //添加到链表末尾
        }
        //定义结果集
        int[] res = new int[link.size()];
        //初始化结果集
        Arrays.fill(res,-1);
        res[link.size()-1] = 0;
        //遍历链表
        for (int i = 1; i < link.size()-1; i++) {
            for (int j = i+1; j < link.size(); j++) {
                if (link.get(i)<link.get(j)){
                    //res[i] = link.get(j);
                    res[i] = j;
                    break;
                }
            }
            if (res[i]==-1){
                res[i] = 0;
            }
        }
        for (int i = 1; i < res.length; i++) {
            System.out.print(res[i]+" ");
        }
    }
}


目录
打赏
0
0
0
0
38
分享
相关文章
【Leetcode 2487】从链表中移除节点 —— 单调栈
解题思路:维持一个单调递增栈,当栈为空时,记录当前节点为头节点;否则当前节点为栈顶节点的后继节点
【每日一题Day254】LC445两数相加Ⅱ | 链表反转 栈
【每日一题Day254】LC445两数相加Ⅱ | 链表反转 栈
88 0
Python实现数据结构(如:链表、栈、队列等)。
Python实现数据结构(如:链表、栈、队列等)。
318 0
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
237 64
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式
在C语言中,数据结构是构建高效程序的基石。本文探讨了数组、链表、栈、队列、树和图等常见数据结构的特点、应用及实现方式,强调了合理选择数据结构的重要性,并通过案例分析展示了其在实际项目中的应用,旨在帮助读者提升编程能力。
196 5
|
8月前
|
数据结构之购物车系统(链表和栈)
本文介绍了基于链表和栈的购物车系统的设计与实现。该系统通过命令行界面提供商品管理、购物车查看、结算等功能,支持用户便捷地管理购物清单。核心代码定义了商品、购物车商品节点和购物车的数据结构,并实现了添加、删除商品、查看购物车内容及结算等操作。算法分析显示,系统在处理小规模购物车时表现良好,但在大规模购物车操作下可能存在性能瓶颈。
182 0
线性表、链表、栈和队列的初始化
线性表、链表、栈和队列的初始化
71 1
栈和链表的区分
栈和链表的区分
93 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等

登录插画

登录以查看您的控制台资源

管理云资源
状态一览
快捷访问