单调递减栈的使用

1.问题描述
给定一个无序的循环数组（循环数组 即数组的最后一个元素的下一个元素为数组的第一个元素）
输出 数组每一个元素的 下一个第一个比该元素大的元素 没有则输出-1

示例：输入 1，2，1
输出 2，-1，2

解题思路：
1.效率不高的方向： 对数组内的每一个元素向后循环遍历 直到循环到自己或者找到比自己大的元素输出

2.正确思路：
如果数组中某一段元素单调不递增 如 8，5，5，4，10
则 比8大的第一个元素10 一定也是 5,5,4 的第一个大的元素 这样 就只需要去找比8 大的元素 就行了 减少循环比较的次数

3.单调递减栈的应用

1. 将数组 copy一份放到后面 变成 长度*2的数组 1,2,1——-> 1,2,1,1,2,1 准备结果数组 {-1，-1，-1}
2. 依次遍历数组 元素为item
3. 如果栈为空 item 压入栈
4. 如果栈不为空 依次比较栈顶元素和 当前循环变量的大小 如果栈顶元素小于 当前变量 输出栈顶元素 既栈顶元素的第一个比它大的元素为 item
5. 依次比较栈顶元素 直到栈为空 或者栈顶元素大于等于 item
6. item 压入栈

4.具体代码 c#

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
namespace nextMax
{
     class Program     
     {
         struct item
         {
             public int value;
             public int index;
             public item(int v,int ide)
             {
                  value = v;
                  index = ide;
             }
         }
        static void Main(string[] args)
        {
             int[] p = new int[3] { 1, 2, 1 };
             int[] res=NextGreaterElements(p);
             for (int i = 0; i < res.Length; i++)
               {
                  Console.WriteLine(res[i]);
               }
             Console.ReadKey();
        }
       public static int[] NextGreaterElements(int[] nums)
       {
             Stack sigle = new Stack();
             //定义一个字典 用来存 值的下标 key=nums[i] value=i
             Dictionary<int, int> indexDic = new Dictionary<int, int>();
             int[] res = new int[nums.Length];
             for (int i = 0; i < nums.Length; i++)
             {
                  res[i] = -1;
             }
             //遍历两遍数组
             for (int s = 0; s < nums.Length * 2; s++)
             {
                  int v = s % nums.Length;
                  int k= nums[v];   
                  if (sigle.Count == 0)
                  {
                      sigle.Push(new item(k,v));
                  }
                  else
                  {
                      //和栈顶元素比较 
                      while (sigle.Count>0 && sigle.Peek().value < k)
                         {
                            item y = sigle.Pop();
                            res[y.index] = k;
                         }
                     sigle.Push(new item(k, v));
                 }
            }
            return res;
       }
   }
}