Алгоритъм, реализиращ стек със стандартни функции за натискане и изскачане и допълнителна функция min в O (1)
И така, оценката на времето за работа на функцията push, pop и min е O (1).
Крайностите не се променят често. Всъщност минимумът може да се промени само при добавяне на нов елемент.
Едно решение е да се сравнят добавените елементи с минималната стойност. Когато минималната стойност (minValue) бъде премахната от стека, трябва да "претърсите" целия стек в търсене на нов минимум. За съжаление това нарушава ограничението по време на изпълнение O (1).
Ако проследим минимума във всяко състояние, тогава лесно можем да разпознаем минималния елемент. Например, можете да запишете текущия минимален елемент за всеки възел.След това, за да намерите min, е достатъчно да "натиснете" отгоре и да видите кой елемент е минималният.
Веднага щом даден елемент се избута в стека, локалният минимум става глобален.
Решението има един недостатък - ако трябва да се справите с огромен стек, проследяването на минималния елемент ще изисква много ресурси. Има ли по-добро решение?
Можете да оптимизирате кода, като използвате допълнителен стек, който ще проследява минимумите.
Защо това решение е по-ефективно? Да предположим, че работим с огромен стек, първият вмъкнат елемент автоматично ще стане минимумът. Първото решение трябва да съхранява n числа, където n е размерът на стека. Във второто решение е достатъчно да запазите няколко парчета данни.
- Образователни и вдъхновяващи функции на изкуството
- Глюкагон какво е това, функции, хормон
- CALC е чудесен заместител на стандартния калкулатор
- Образователна функция (изкуство като катарзис), Вдъхновяваща функция (изкуство като предложение),
- Видове и функции на лизинговите дейности