在集合中找到大于它们的数字

Question

假设我们有一组数字,如{16,17,4,3,5,2}.现在的目标是找到那些大于集合中其余数字的数字,同时与它们的正确元素进行比较.

表示16与17相比较少,不能考虑.虽然17比较4,3 5和2总是更大,因此将被考虑.同样地,将丢弃小于5的大于3的邻接.但5比2更大.并且因为2是最右边的元素将始终被考虑.我已经编写了以下程序,它可以工作.

using System;
using System.Collections.Generic;
using System.Linq;

namespace ConsoleApplication2
{
    class Program
    {
        static void Main(string[] args)
        {

            var intCollection = new List<int>() { 16,17,4,3,5,2 };
            var discardedElements = new List<int>();

             for(int i=0;i< intCollection.Count;i++)
             {
                 for(int j=i+1;j< intCollection.Count; j++)
                 {
                     if (intCollection[i] < intCollection[j])
                     {
                         discardedElements.Add(intCollection[i]);
                     }
                 }
             }
             Console.WriteLine("Successful elements are");
             intCollection.Except(discardedElements).ToList().ForEach(i => Console.WriteLine("{0}", i));
             Console.ReadKey();
        } 
    }
}

结果

Successful elements are
17
5
2

但是这个程序不是优化程序.针对同样问题的任何更好的算法？

NB~该程序虽然显然没有任何实时使用,但它将有助于改进算法.

Answer 1

您可以从右向左过滤并过滤增加的数字序列

例:

class Program
{
    static void Main( String[] args )
    {
        var intCollection = new List<Int32>() { 16, 17, 4, 3, 5, 2 };
        var intResults = new List<Int32>();
        var currentMaxValue = Int32.MinValue;

        for ( Int32 i = intCollection.Count - 1; i >= 0; --i )
        {
            if ( intCollection[ i ] > currentMaxValue )
            {
                currentMaxValue = intCollection[ i ];
                intResults.Insert( 0, intCollection[ i ] );
            }
        }

        Console.WriteLine( "Successful elements are" );
        intResults.ForEach( i => Console.WriteLine( "{0}", i ) );
        Console.ReadKey();
    }
}