前言
单调栈对新手来说不好理解，但链表就特别简单，但在有时间限制的竞赛中，很容易超时，因此如果实在要使用链表，注意使用链表的类型，Java提供的两种实现链表的方式：
LinkedList 适用于大量增删的操作，这道题不适合
ArrayList 适用于大量遍历搜索的操作，这道题因为需要一直搜索遍历链表直到找到比自己大的结点，所以更适用！
二者时间区别见下图:
LinkedList：
ArrayList：
但能理解单调栈最好了：
单调栈实现
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]+" "); } } }
