洛谷(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]+" ");
        }
    }
}


相关文章
|
7月前
【Leetcode 2487】从链表中移除节点 —— 单调栈
解题思路:维持一个单调递增栈,当栈为空时,记录当前节点为头节点;否则当前节点为栈顶节点的后继节点
|
7月前
|
C++
数据结构01-线性结构-链表栈队列-栈篇
数据结构01-线性结构-链表栈队列-栈篇
|
7月前
|
存储
【每日一题Day254】LC445两数相加Ⅱ | 链表反转 栈
【每日一题Day254】LC445两数相加Ⅱ | 链表反转 栈
46 0
|
7月前
|
Python
Python实现数据结构(如:链表、栈、队列等)。
Python实现数据结构(如:链表、栈、队列等)。
279 0
|
2月前
|
存储 算法 搜索推荐
探索常见数据结构:数组、链表、栈、队列、树和图
探索常见数据结构:数组、链表、栈、队列、树和图
112 64
|
6月前
|
数据安全/隐私保护
第2章 栈、队列、链表
第2章 栈、队列、链表
|
6月前
栈和链表的区分
栈和链表的区分
23 0
|
7月前
|
存储
线性表、链表、栈和队列的初始化
线性表、链表、栈和队列的初始化
41 1
|
7月前
|
存储 调度 C语言
链表,栈,队列的区别及其应用
链表,栈,队列的区别及其应用
|
7月前
|
Go Python 算法
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点
769 0
Python每日一练(20230412) 队列实现栈、二叉树序列化、交换链表节点