معرفی
در این مقاله، یاد خواهید گرفت که چگونه عنصر بزرگتر بعدی هر عنصر را پیدا کنید.
بیان مسأله
با توجه به یک آرایه، برای هر عنصر، عنصر بزرگتر بعدی یا سمت راست عنصر را پیدا کنید. اگر عنصر بزرگ تری وجود ندارد، مقدار را روی -1 قرار دهید. در اینجا یک مثال وجود دارد، آرایه [4، 2، 5، 9، 2، 3] به [5، 5، 9، -1، 3، -1] منجر می شود.
رویکرد 1
سادهترین راه برای حل این مشکل استفاده از حلقههای تودرتو، یکی روی هر عنصر، و سپس حلقه روی همه عناصر در سمت راست آن است. اگر عنصر بزرگتری پیدا کنیم، آن را ذخیره میکنیم و ادامه میدهیم یا -1 را ذخیره میکنیم.
پیچیدگی زمانی - O (N^2)
پیچیدگی فضا - O (1).
این یک الگوریتم بسیار کند است زیرا هر عنصر به طور بالقوه باید از هر عنصر به سمت راست بازدید کند. اما الگوریتم از فضای اضافی استفاده نمی کند. در اینجا یک کد نمونه در سی شارپ آمده است که این الگوریتم را نشان می دهد:
- class Program
- {
- static void Main(string[] args)
- {
- int[] array = new int[] { 4, 2, 5, 9, 2, 3 };
- int[] result = Approach1(array);
- //result is [ 5, 5, 9, -1, 3, -1 ]
- }
- static int[] Approach1(int[] array)
- {
- int[] result = new int[array.Length];
- for (int i = 0; i < array.Length; i++)
- {
- //firstly assume the element has no next greater element
- result[i] = -1;
- //find next greater element by iterating over the rest
- for (int j = i + 1; j < array.Length; j++)
- {
- //found the next greater element
- if (array[j] > array[i])
- {
- result[i] = array[j];
- break;
- }
- }
- }
- return result;
- }
- }
رویکرد 2
این رویکرد به یک پشته نیاز دارد تا شاخص عناصری را که عناصر بزرگ بعدی خود را ندارند حفظ کند. در این راه حل، ما از هر عنصر بازدید می کنیم تا بررسی کنیم که آیا مقدار عنصر فعلی بیشتر از عنصر بالای پشته است یا خیر.
پیچیدگی زمانی - O(N)
پیچیدگی فضا - O(N).
سریع است زیرا ما یک بار از هر عنصر بازدید می کنیم. در بدترین حالت، ما باید تمام عناصر را با استفاده از فضای اضافی زیادی در پشته قرار دهیم. شبه کدی که این راه حل را نشان می دهد در زیر با استفاده از C# نشان داده شده است:
- class Program
- {
- static void Main(string[] args)
- {
- int[] array = new int[] { 4, 2, 5, 9, 2, 3 };
- int[] result = Approach2(array);
- //result is [ 5, 5, 9, -1, 3, -1 ]
- }
- static int[] Approach2(int[] array)
- {
- Stack<int> nextGreaterIndex = new Stack<int>();
- int[] result = new int[array.Length];
- for (int i = 0; i < array.Length; i++)
- {
- //check if this element has any next greater element
- while (nextGreaterIndex.Count > 0)
- {
- if (array[i] > array[nextGreaterIndex.Peek()])
- {
- result[nextGreaterIndex.Peek()] = array[i];
- nextGreaterIndex.Pop();
- }
- else
- break;
- }
- nextGreaterIndex.Push(i);
- }
- //all elements left will have no next greater element
- while (nextGreaterIndex.Count > 0)
- {
- result[nextGreaterIndex.Peek()] = -1;
- nextGreaterIndex.Pop();
- }
- return result;
- }
- }
رویکرد 3
این راه حل بسیار شبیه به روش 2 فوق است. تنها تفاوت این است که ما عناصر را به ترتیب معکوس بازدید خواهیم کرد. دلیل آن وجود یک عنصر بزرگتر در پشته برای عنصر فعلی است. بقیه پیچیدگی های زمان و مکان مانند رویکرد 2 است. در زیر یک نمونه کد برای این رویکرد در سی شارپ آمده است:
- class Program
- {
- static void Main(string[] args)
- {
- int[] array = new int[] { 4, 2, 5, 9, 2, 3 };
- int[] result = Approach3(array);
- //result is [ 5, 5, 9, -1, 3, -1 ]
- }
- static int[] Approach3(int[] array)
- {
- Stack<int> nextGreaterIndex = new Stack<int>();
- int[] result = new int[array.Length];
- //reverse iteration
- for (int i = array.Length – 1; i >= 0; i–)
- {
- //pop untill the greater element
- while (nextGreaterIndex.Count > 0 && array[nextGreaterIndex.Peek()] <= array[i])
- nextGreaterIndex.Pop();
- //assign result with the top element of the stack
- result[i] = nextGreaterIndex.Count > 0 ? array[nextGreaterIndex.Peek()] : -1;
- nextGreaterIndex.Push(i);
- }
- return result;
- }
- }