Algoritmik d\u00fc\u015f\u00fcnme becerileri, modern yaz\u0131l\u0131m geli\u015ftirmenin temel ta\u015flar\u0131ndan biridir. \u00d6zellikle veri yap\u0131lar\u0131 ve algoritmalar, karma\u015f\u0131k problemleri \u00e7\u00f6zmek i\u00e7in bize g\u00fc\u00e7l\u00fc ara\u00e7lar sunar. Bu makalede, s\u0131k\u00e7a kar\u015f\u0131la\u015f\u0131lan ve ilk bak\u0131\u015fta basit gibi g\u00f6r\u00fcnen ancak verimli \u00e7\u00f6z\u00fcmler gerektiren “Next Greater Element I” (Bir Sonraki B\u00fcy\u00fck Eleman I) problemine odaklanaca\u011f\u0131z. Bu problemi, ad\u0131n\u0131 belki de ilk kez duydu\u011funuz ancak son derece etkili bir veri yap\u0131s\u0131 olan “Monotonik Y\u0131\u011f\u0131n” (Monotonic Stack) kullanarak nas\u0131l \u00e7\u00f6zebilece\u011fimizi ad\u0131m ad\u0131m inceleyece\u011fiz. Bu teknik, sadece bu \u00f6zel problemi de\u011fil, benzer bir\u00e7ok senaryoda da performans\u0131 \u00f6nemli \u00f6l\u00e7\u00fcde art\u0131ran bir yakla\u015f\u0131m sunar. Haz\u0131rlan\u0131n, \u00e7\u00fcnk\u00fc algoritmik d\u00fc\u015f\u00fcncenizi bir \u00fcst seviyeye ta\u015f\u0131yacak pratik bilgilerle dolu bir yolculu\u011fa \u00e7\u0131k\u0131yoruz.<\/p>\n
Hayat\u0131n her alan\u0131nda, bir dizi veya listedeki elemanlar aras\u0131nda belirli ili\u015fkileri bulmam\u0131z gerekebilir. \u00d6rne\u011fin, bir hisse senedi fiyat listesinde, belirli bir g\u00fcnk\u00fc fiyattan sonraki ilk daha y\u00fcksek fiyat\u0131 ne zaman g\u00f6rd\u00fc\u011f\u00fcm\u00fcz\u00fc merak edebiliriz. Veya bir veri ak\u0131\u015f\u0131nda, mevcut de\u011ferden daha b\u00fcy\u00fck olan bir sonraki de\u011feri h\u0131zl\u0131ca tespit etmemiz gerekebilir. \u0130\u015fte tam da bu noktada “Next Greater Element” (NGE) problemi devreye girer. Bu problem, bir dizideki her eleman i\u00e7in, o elemandan sonra gelen ve kendisinden daha b\u00fcy\u00fck olan ilk eleman\u0131 bulmay\u0131 hedefler.<\/p>\n
NGE problemi, sadece teorik bir kavram olmaktan \u00f6te, yaz\u0131l\u0131m geli\u015ftirmenin bir\u00e7ok alan\u0131nda pratik uygulamalara sahiptir. \u00d6rne\u011fin, derleyici tasar\u0131m\u0131nda s\u00f6zdizimi analizi yaparken, finansal piyasalarda hisse senedi verilerini analiz ederken, web trafi\u011fi analizinde anormallikleri tespit ederken veya hatta oyun geli\u015ftirme gibi farkl\u0131 disiplinlerde bile kar\u015f\u0131m\u0131za \u00e7\u0131kabilir. Bu t\u00fcr senaryolarda, b\u00fcy\u00fck veri k\u00fcmeleriyle \u00e7al\u0131\u015ft\u0131\u011f\u0131m\u0131z d\u00fc\u015f\u00fcn\u00fcld\u00fc\u011f\u00fcnde, verimsiz \u00e7\u00f6z\u00fcmler performans sorunlar\u0131na yol a\u00e7abilir. Dolay\u0131s\u0131yla, bu problemi h\u0131zl\u0131 ve etkin bir \u015fekilde \u00e7\u00f6zebilmek, geli\u015ftiriciler i\u00e7in kritik bir beceridir. Basit bir kaba kuvvet (brute-force) yakla\u015f\u0131m\u0131, her eleman i\u00e7in dizinin geri kalan\u0131n\u0131 tarayarak \u00e7\u00f6z\u00fcme ula\u015fabilir ancak bu, \u00f6zellikle b\u00fcy\u00fck dizilerde kabul edilemez derecede yava\u015f olabilir. Bu nedenle, daha sofistike ve optimize edilmi\u015f bir yakla\u015f\u0131ma ihtiya\u00e7 duyar\u0131z ki, bu da bizi Monotonik Y\u0131\u011f\u0131n gibi g\u00fc\u00e7l\u00fc veri yap\u0131lar\u0131na y\u00f6nlendirir. Bu makalenin ilerleyen b\u00f6l\u00fcmlerinde, bu verimli \u00e7\u00f6z\u00fcm\u00fcn temel prensiplerini ve ad\u0131m ad\u0131m uygulamas\u0131n\u0131 detayl\u0131ca ele alaca\u011f\u0131z.<\/p>\n
“Next Greater Element I” (NGE I) problemi, iki dizi verildi\u011finde ortaya \u00e7\u0131kar: Bu kavram\u0131 daha iyi anlamak i\u00e7in bir \u00f6rnek d\u00fc\u015f\u00fcnelim: \u00c7\u0131kt\u0131 dizisi Peki, bu problemi kaba kuvvet (brute-force) yakla\u015f\u0131m\u0131yla nas\u0131l \u00e7\u00f6zeriz? Algoritmik problemlerle u\u011fra\u015f\u0131rken kar\u015f\u0131m\u0131za \u00e7\u0131kan en temel ve g\u00fc\u00e7l\u00fc veri yap\u0131lar\u0131ndan biri y\u0131\u011f\u0131nd\u0131r (stack). Y\u0131\u011f\u0131n, belirli bir prensibe g\u00f6re \u00e7al\u0131\u015fan, elemanlar\u0131n eklenmesi ve \u00e7\u0131kar\u0131lmas\u0131 i\u00e7in k\u0131s\u0131tl\u0131 bir eri\u015fim sa\u011flayan do\u011frusal bir veri yap\u0131s\u0131d\u0131r. Bu prensip, “Son Giren \u0130lk \u00c7\u0131kar” (LIFO – Last-In, First-Out) olarak bilinir. Bir y\u0131\u011f\u0131n\u0131, \u00fcst \u00fcste dizilmi\u015f tabaklar veya bir dergi y\u0131\u011f\u0131n\u0131 gibi d\u00fc\u015f\u00fcnebilirsiniz; en son koydu\u011funuz taba\u011f\u0131 veya dergiyi, alttakilere ula\u015fmadan \u00f6nce ilk olarak al\u0131rs\u0131n\u0131z.<\/p>\n Y\u0131\u011f\u0131n veri yap\u0131s\u0131n\u0131n temel operasyonlar\u0131 \u015funlard\u0131r:<\/p>\n Y\u0131\u011f\u0131nlar, bilgisayar bilimlerinde \u00e7ok \u00e7e\u015fitli alanlarda kullan\u0131l\u0131r. \u00d6rne\u011fin, bir program\u0131n fonksiyon \u00e7a\u011fr\u0131lar\u0131n\u0131 y\u00f6neten \u00e7a\u011fr\u0131 y\u0131\u011f\u0131n\u0131 (call stack), y\u0131\u011f\u0131n\u0131n en bilinen uygulamalar\u0131ndan biridir. Bir fonksiyon \u00e7a\u011fr\u0131ld\u0131\u011f\u0131nda, parametreleri ve yerel de\u011fi\u015fkenleri y\u0131\u011f\u0131na itilir; fonksiyon tamamland\u0131\u011f\u0131nda ise y\u0131\u011f\u0131ndan \u00e7\u0131kar\u0131l\u0131r. Ayr\u0131ca, parantez e\u015fle\u015ftirme (\u00f6rne\u011fin, bir ifadede a\u00e7\u0131lan ve kapanan parantezlerin do\u011fru s\u0131rada olup olmad\u0131\u011f\u0131n\u0131 kontrol etme), taray\u0131c\u0131lar\u0131n geri\/ileri d\u00fc\u011fmeleri, metin edit\u00f6rlerindeki “geri al” (undo) i\u015flevi ve derinlemesine arama (DFS) algoritmalar\u0131 gibi bir\u00e7ok senaryoda y\u0131\u011f\u0131nlar hayati bir rol oynar.<\/p>\n NGE problemi gibi elemanlar aras\u0131ndaki s\u0131ralama ili\u015fkilerini bulmaya \u00e7al\u0131\u015ft\u0131\u011f\u0131m\u0131z problemlerde, y\u0131\u011f\u0131n\u0131n LIFO \u00f6zelli\u011fi, bize elemanlar\u0131 belirli bir d\u00fczende ge\u00e7ici olarak saklama ve gerekti\u011finde h\u0131zl\u0131ca eri\u015fme imkan\u0131 sunar. \u00d6zellikle, “Monotonik Y\u0131\u011f\u0131n” ad\u0131 verilen \u00f6zel bir y\u0131\u011f\u0131n t\u00fcr\u00fc, bu t\u00fcr s\u0131ralama problemlerini \u00e7ok daha verimli bir \u015fekilde \u00e7\u00f6zmemize olanak tan\u0131r. Bir sonraki b\u00f6l\u00fcmde, monotonik y\u0131\u011f\u0131n\u0131n ne oldu\u011funu ve NGE problemindeki g\u00fcc\u00fcn\u00fc daha yak\u0131ndan inceleyece\u011fiz.<\/p>\n Y\u0131\u011f\u0131n veri yap\u0131s\u0131n\u0131n temel prensiplerini anlad\u0131ktan sonra, algoritmik verimlili\u011fi art\u0131rmak i\u00e7in y\u0131\u011f\u0131n\u0131n daha \u00f6zel bir formu olan “Monotonik Y\u0131\u011f\u0131n”a ge\u00e7ebiliriz. Monotonik y\u0131\u011f\u0131n, ad\u0131ndan da anla\u015f\u0131laca\u011f\u0131 gibi, elemanlar\u0131n\u0131n ya s\u00fcrekli artan (monotonically increasing) ya da s\u00fcrekli azalan (monotonically decreasing) bir d\u00fczende tutuldu\u011fu bir y\u0131\u011f\u0131nd\u0131r. Bu \u00f6zelli\u011fi sayesinde, belirli bir elemandan sonra gelen ilk b\u00fcy\u00fck veya ilk k\u00fc\u00e7\u00fck eleman\u0131 bulma gibi problemlerde ola\u011fan\u00fcst\u00fc bir performans sergiler.<\/p>\n Monotonik y\u0131\u011f\u0131n\u0131n iki ana tipi vard\u0131r:<\/p>\n Peki, bu “monotonik” (tekd\u00fcze) \u00f6zellik neden bu kadar \u00f6nemlidir? NGE gibi bir problemi ele al\u0131rken, her eleman i\u00e7in kendisinden sonraki ilk b\u00fcy\u00fck eleman\u0131 arar\u0131z. Geleneksel bir y\u0131\u011f\u0131nla bu i\u015flemi yapmak, her seferinde y\u0131\u011f\u0131n\u0131 taramay\u0131 gerektirebilir. Ancak monotonik bir y\u0131\u011f\u0131n kulland\u0131\u011f\u0131m\u0131zda, y\u0131\u011f\u0131n\u0131n tepesindeki elemanlar her zaman belirli bir s\u0131ralamay\u0131 korudu\u011fu i\u00e7in, yeni bir eleman geldi\u011finde, y\u0131\u011f\u0131ndaki hangi elemanlar\u0131n bu yeni eleman taraf\u0131ndan “Next Greater Element” olarak belirlendi\u011fini h\u0131zl\u0131ca anlayabiliriz. \u00d6rne\u011fin, azalan monotonik bir y\u0131\u011f\u0131nda, yeni gelen bir say\u0131, y\u0131\u011f\u0131n\u0131n tepesindeki say\u0131dan b\u00fcy\u00fckse, y\u0131\u011f\u0131ndaki tepedeki say\u0131lar\u0131n “Next Greater Element”i bulunmu\u015f demektir. Bu elemanlar\u0131 y\u0131\u011f\u0131ndan \u00e7\u0131kar\u0131r\u0131z ve yeni gelen say\u0131y\u0131 ekleriz.<\/p>\n Bu yakla\u015f\u0131m\u0131n en b\u00fcy\u00fck avantaj\u0131, her eleman\u0131n y\u0131\u011f\u0131na en fazla bir kez eklenip en fazla bir kez \u00e7\u0131kar\u0131lmas\u0131d\u0131r. Bu da bize Next Greater Element I (NGE I) problemini Monotonik Y\u0131\u011f\u0131n kullanarak \u00e7\u00f6zmek, kaba kuvvet yakla\u015f\u0131m\u0131na g\u00f6re \u00e7ok daha verimli bir y\u00f6ntem sunar. Bu \u00e7\u00f6z\u00fcm\u00fcn temelinde, \u0130\u015fte ad\u0131m ad\u0131m algoritma:<\/p>\n Bu ad\u0131m, y\u0131\u011f\u0131ndaki kendisinden k\u00fc\u00e7\u00fck t\u00fcm elemanlar\u0131n NGE’sini bulmam\u0131z\u0131 sa\u011flar. Y\u0131\u011f\u0131n, \u015eimdi Bu algoritma, \u015eimdi, Next Greater Element I problemini Monotonik Y\u0131\u011f\u0131n kullanarak nas\u0131l \u00e7\u00f6zd\u00fc\u011f\u00fcm\u00fcz\u00fc somut bir \u00f6rnek ve Python kodu \u00fczerinden inceleyelim. Bu, algoritman\u0131n i\u015fleyi\u015fini daha net anlaman\u0131za yard\u0131mc\u0131 olacakt\u0131r.<\/p>\n \u00d6rnek Diziler:<\/strong> Algoritma Takibi:<\/strong><\/p>\n Nihai Sonu\u00e7 Dizisi:<\/strong> Python Kodu:<\/strong><\/p>\n Yukar\u0131daki Python kodu, ad\u0131m ad\u0131m a\u00e7\u0131klanan algoritmay\u0131 uygulamaktad\u0131r. Monotonik y\u0131\u011f\u0131nlar, sadece algoritmik m\u00fclakat sorular\u0131nda kar\u015f\u0131m\u0131za \u00e7\u0131kan soyut bir kavram de\u011fildir; aksine, bir\u00e7ok ger\u00e7ek d\u00fcnya probleminde verimli \u00e7\u00f6z\u00fcmler sunan g\u00fc\u00e7l\u00fc bir ara\u00e7t\u0131r. NGE I problemi, bu uygulaman\u0131n temel bir \u00f6rne\u011fi olsa da, monotonik y\u0131\u011f\u0131n\u0131n yetenekleri \u00e7ok daha geni\u015ftir. \u0130\u015fte baz\u0131 pratik uygulama alanlar\u0131:<\/p>\n Hisse senedi piyasalar\u0131nda yat\u0131r\u0131mc\u0131lar ve analistler, bir hisse senedinin fiyat\u0131n\u0131n belirli bir g\u00fcn ka\u00e7 g\u00fcnd\u00fcr mevcut fiyattan daha y\u00fcksek olmad\u0131\u011f\u0131n\u0131 merak edebilirler. Bu, \"Stock Span Problem\" olarak bilinir ve monotonik y\u0131\u011f\u0131n kullan\u0131larak B\u00fcy\u00fck veri k\u00fcmeleriyle \u00e7al\u0131\u015f\u0131rken, zaman serisi verilerinde (\u00f6rne\u011fin, s\u0131cakl\u0131k \u00f6l\u00e7\u00fcmleri, sunucu y\u00fckleri, sat\u0131\u015f rakamlar\u0131) belirli trendleri veya anormallikleri tespit etmek \u00f6nemlidir. Monotonik y\u0131\u011f\u0131n, bir veri noktas\u0131ndan sonra gelen ilk b\u00fcy\u00fck veya ilk k\u00fc\u00e7\u00fck de\u011feri bulmak i\u00e7in kullan\u0131labilir. Bu, ani y\u00fckseli\u015fleri (spikes) veya d\u00fc\u015f\u00fc\u015fleri (dips) tespit etmeye yard\u0131mc\u0131 olur, b\u00f6ylece sistem y\u00f6neticileri veya veri analistleri h\u0131zl\u0131ca m\u00fcdahale edebilir. \u00d6rne\u011fin, bir sunucunun CPU kullan\u0131m\u0131n\u0131n belirli bir e\u015fi\u011fi a\u015ft\u0131\u011f\u0131 ilk zaman dilimini tespit etmek i\u00e7in kullan\u0131labilir.<\/p>\n<\/li>\n G\u00f6r\u00fcnt\u00fc i\u015flemede veya bilgisayar grafiklerinde, bir histogramda (s\u00fctun grafi\u011fi) yer alan en b\u00fcy\u00fck dikd\u00f6rtgen alan\u0131 bulmak \u00f6nemli bir problemdir. Bu problem, g\u00f6r\u00fcnt\u00fcdeki belirli bir \u00f6zelli\u011fin yo\u011funlu\u011funu veya da\u011f\u0131l\u0131m\u0131n\u0131 analiz etmek i\u00e7in kullan\u0131labilir. Monotonik y\u0131\u011f\u0131n, her s\u00fctun i\u00e7in kendisinden daha k\u00fc\u00e7\u00fck olan ilk sol ve ilk sa\u011f s\u00fctunlar\u0131 bulmaya yard\u0131mc\u0131 olarak bu problemi Programlama dillerinde parantezlerin, k\u00fcme parantezlerinin veya k\u00f6\u015feli parantezlerin do\u011fru \u015fekilde e\u015fle\u015fip e\u015fle\u015fmedi\u011fini kontrol etmek derleyicilerin temel g\u00f6revidir. Y\u0131\u011f\u0131nlar bu i\u015flem i\u00e7in zaten yayg\u0131n olarak kullan\u0131l\u0131rken, monotonik y\u0131\u011f\u0131nlar daha karma\u015f\u0131k s\u00f6zdizimsel yap\u0131lar\u0131n analizinde, \u00f6rne\u011fin operat\u00f6r \u00f6nceli\u011fi gibi durumlarda, belirli bir operat\u00f6rden sonra gelen ilk y\u00fcksek \u00f6ncelikli operat\u00f6r\u00fc bulmak gibi senaryolarda da yard\u0131mc\u0131 olabilir.<\/p>\n<\/li>\n IoT cihazlar\u0131ndan gelen sens\u00f6r verileri genellikle s\u00fcrekli bir ak\u0131\u015f halindedir. Bu verilerde, belirli bir e\u015fi\u011fi a\u015fan veya belirli bir de\u011ferden sonra gelen ilk b\u00fcy\u00fck\/k\u00fc\u00e7\u00fck anormalli\u011fi tespit etmek, sistemlerin otonom kararlar almas\u0131 veya uyar\u0131lar \u00fcretmesi i\u00e7in kritik \u00f6neme sahiptir. Monotonik y\u0131\u011f\u0131n, bu t\u00fcr ger\u00e7ek zamanl\u0131 veri ak\u0131\u015flar\u0131nda d\u00fc\u015f\u00fck gecikmeyle anormallik tespiti yapmaya olanak tan\u0131r.<\/p>\n<\/li>\n<\/ol>\n G\u00f6r\u00fcld\u00fc\u011f\u00fc \u00fczere, monotonik y\u0131\u011f\u0131n, sadece basit bir algoritmik hile olmaktan \u00e7ok, \u00e7e\u015fitli sekt\u00f6rlerdeki karma\u015f\u0131k problemlerin verimli bir \u015fekilde \u00e7\u00f6z\u00fclmesini sa\u011flayan \u00e7ok y\u00f6nl\u00fc bir ara\u00e7t\u0131r. Bu veri yap\u0131s\u0131n\u0131 anlamak ve uygulamak, bir yaz\u0131l\u0131m geli\u015ftiricinin problem \u00e7\u00f6zme yetene\u011fini \u00f6nemli \u00f6l\u00e7\u00fcde art\u0131r\u0131r.<\/p>\n Bu makalede, \"Next Greater Element I\" (Bir Sonraki B\u00fcy\u00fck Eleman I) problemini derinlemesine inceledik ve bu problemi \u00e7\u00f6zmek i\u00e7in Monotonik Y\u0131\u011f\u0131n ad\u0131 verilen g\u00fc\u00e7l\u00fc bir veri yap\u0131s\u0131n\u0131n nas\u0131l kullan\u0131labilece\u011fini \u00f6\u011frendik. Ba\u015flang\u0131\u00e7ta, kaba kuvvet (brute-force) yakla\u015f\u0131m\u0131n\u0131n neden yetersiz kald\u0131\u011f\u0131n\u0131 ve neden daha verimli bir \u00e7\u00f6z\u00fcme ihtiya\u00e7 duydu\u011fumuzu g\u00f6rd\u00fck. Ard\u0131ndan, y\u0131\u011f\u0131n veri yap\u0131s\u0131n\u0131n temel prensiplerini ve LIFO (Son Giren \u0130lk \u00c7\u0131kar) mant\u0131\u011f\u0131n\u0131 kavrad\u0131k. Bu temeller \u00fczerine in\u015fa ederek, monotonik y\u0131\u011f\u0131n\u0131n ne oldu\u011funu, neden bu kadar etkili oldu\u011funu ve elemanlar\u0131 nas\u0131l s\u00fcrekli artan veya azalan bir d\u00fczende tuttu\u011funu detayland\u0131rd\u0131k.<\/p>\n Monotonik y\u0131\u011f\u0131n kullanarak NGE I problemini ad\u0131m ad\u0131m nas\u0131l \u00e7\u00f6zd\u00fc\u011f\u00fcm\u00fcz\u00fc, Python kodu ve somut bir \u00f6rnek \u00fczerinden takip ettik. Bu sayede, algoritman\u0131n her bir a\u015famas\u0131n\u0131n nas\u0131l \u00e7al\u0131\u015ft\u0131\u011f\u0131n\u0131 ve \u00d6zetle, monotonik y\u0131\u011f\u0131n, algoritmik d\u00fc\u015f\u00fcnme repertuvar\u0131n\u0131za ekleyebilece\u011finiz de\u011ferli bir tekniktir. Bu makalede edindi\u011finiz bilgilerle, benzer s\u0131ralama problemlerini \u00e7ok daha verimli bir \u015fekilde \u00e7\u00f6zebilir, yaz\u0131l\u0131m\u0131n\u0131z\u0131n performans\u0131n\u0131 art\u0131rabilir ve daha karma\u015f\u0131k algoritmik zorluklar\u0131n \u00fcstesinden gelebilirsiniz. Gelecekte, \"Next Greater Element II\" (dairesel diziler i\u00e7in), \"Next Smaller Element\" veya \"Largest Rectangle in Histogram\" gibi di\u011fer monotonik y\u0131\u011f\u0131n problemlerini ke\u015ffederek bilginizi daha da geni\u015fletebilirsiniz. Unutmay\u0131n, iyi tasarlanm\u0131\u015f algoritmalar, teknolojik d\u00fcnyan\u0131n temelini olu\u015fturur ve bu alandaki yetkinli\u011finiz, sizi bir ad\u0131m \u00f6ne \u00e7\u0131karacakt\u0131r.<\/p>\n 1. Next Greater Element I ile Next Greater Element II aras\u0131ndaki fark nedir?<\/strong><\/p>\n Next Greater Element I (NGE I), genellikle iki dizi ( 2. Monotonik y\u0131\u011f\u0131n neden NGE problemlerini kaba kuvvetten daha h\u0131zl\u0131 \u00e7\u00f6zer?<\/strong><\/p>\n Monotonik y\u0131\u011f\u0131n, elemanlar\u0131 belirli bir s\u0131ralama (artan veya azalan) i\u00e7inde tuttu\u011fu i\u00e7in, her eleman i\u00e7in kendisinden sonraki b\u00fcy\u00fck veya k\u00fc\u00e7\u00fck eleman\u0131 bulma s\u00fcrecini optimize eder. Kaba kuvvet y\u00f6ntemi her eleman i\u00e7in dizinin geri kalan\u0131n\u0131 tekrar tekrar tararken ( 3. Monotonik y\u0131\u011f\u0131n sadece \"Next Greater Element\" problemleri i\u00e7in mi kullan\u0131l\u0131r?<\/strong><\/p>\n Hay\u0131r, monotonik y\u0131\u011f\u0131n sadece NGE problemleri i\u00e7in de\u011fil, benzer bir\u00e7ok algoritmik problemde kullan\u0131l\u0131r. \u00d6rne\u011fin, \"Next Smaller Element\" (bir sonraki k\u00fc\u00e7\u00fck eleman), \"Previous Greater Element\" (\u00f6nceki b\u00fcy\u00fck eleman), \"Stock Span Problem\" (hisse senedi kapsam problemi) ve \"Largest Rectangle in Histogram\" (histogramdaki en b\u00fcy\u00fck dikd\u00f6rtgen) gibi problemlerde de etkili \u00e7\u00f6z\u00fcmler sunar. Temel olarak, bir dizideki her eleman i\u00e7in kendisinden \u00f6nce veya sonra gelen ilk belirli ko\u015fulu (b\u00fcy\u00fck\/k\u00fc\u00e7\u00fck) sa\u011flayan eleman\u0131 bulmak gerekti\u011finde monotonik y\u0131\u011f\u0131n g\u00fc\u00e7l\u00fc bir ara\u00e7t\u0131r.<\/p>\nnums1<\/code> ve nums2<\/code>. Burada nums1<\/code> dizisi, nums2<\/code> dizisinin bir alt k\u00fcmesidir. Problem, nums1<\/code> dizisindeki her eleman i\u00e7in, o eleman\u0131n nums2<\/code> dizisindeki konumundan sonra gelen ve kendisinden daha b\u00fcy\u00fck olan ilk<\/b> eleman\u0131 bulmakt\u0131r. E\u011fer b\u00f6yle bir eleman yoksa, o eleman i\u00e7in -1 de\u011feri d\u00f6nd\u00fcr\u00fcl\u00fcr. Bu problem, genellikle tek bir dizi \u00fczerinde “Her eleman i\u00e7in kendisinden sonraki ilk b\u00fcy\u00fck eleman\u0131 bul” \u015feklinde de sorulabilir, ancak NGE I spesifik olarak alt k\u00fcme senaryosuna odaklan\u0131r.<\/p>\n
\nnums1 = [4, 1, 2]<\/code>
\nnums2 = [1, 3, 4, 2]<\/code><\/p>\n\n
nums1<\/code>‘deki 4 i\u00e7in: nums2<\/code>‘de 4’ten sonra gelen ve 4’ten b\u00fcy\u00fck bir eleman yoktur. Sonu\u00e7: -1.<\/li>\nnums1<\/code>‘deki 1 i\u00e7in: nums2<\/code>‘de 1’den sonra gelen ilk b\u00fcy\u00fck eleman 3’t\u00fcr. Sonu\u00e7: 3.<\/li>\nnums1<\/code>‘deki 2 i\u00e7in: nums2<\/code>‘de 2’den sonra gelen ve 2’den b\u00fcy\u00fck bir eleman yoktur. Sonu\u00e7: -1.<\/li>\n<\/ul>\n[-1, 3, -1]<\/code> olacakt\u0131r.<\/p>\n
\nEn basit y\u00f6ntem, nums1<\/code>‘deki her eleman i\u00e7in nums2<\/code>‘de o eleman\u0131 bulmak ve ard\u0131ndan nums2<\/code>‘nin geri kalan\u0131n\u0131 tarayarak kendisinden daha b\u00fcy\u00fck olan ilk eleman\u0131 aramakt\u0131r.
\n\u00d6rne\u011fin, nums1<\/code>‘deki 4’\u00fc ele alal\u0131m. nums2<\/code>‘de 4’\u00fc buluruz (indeks 2). Ard\u0131ndan nums2<\/code>‘nin indeks 3’ten itibaren elemanlar\u0131n\u0131 (yani sadece 2) kontrol ederiz. 2, 4’ten b\u00fcy\u00fck olmad\u0131\u011f\u0131 i\u00e7in, 4 i\u00e7in NGE yoktur ve -1 atar\u0131z.
\nBu yakla\u015f\u0131m, i\u00e7 i\u00e7e d\u00f6ng\u00fcler i\u00e7erdi\u011fi i\u00e7in olduk\u00e7a verimsizdir. nums1<\/code>‘in uzunlu\u011fu m<\/code> ve nums2<\/code>‘nin uzunlu\u011fu n<\/code> ise, her nums1<\/code> eleman\u0131 i\u00e7in nums2<\/code>‘yi taramak O(n)<\/code> zaman al\u0131r. Dolay\u0131s\u0131yla, toplam zaman karma\u015f\u0131kl\u0131\u011f\u0131 O(m * n)<\/code> olacakt\u0131r. E\u011fer m<\/code> ve n<\/code> binlerce, hatta milyonlarca eleman i\u00e7eriyorsa, bu \u00e7\u00f6z\u00fcm kabul edilemez derecede yava\u015f \u00e7al\u0131\u015facakt\u0131r. Bu durum, bizi daha h\u0131zl\u0131 ve daha ak\u0131ll\u0131 bir \u00e7\u00f6z\u00fcm aramaya iter, ki bu da Monotonik Y\u0131\u011f\u0131n gibi geli\u015fmi\u015f veri yap\u0131lar\u0131n\u0131n \u00f6nemini vurgular.<\/p>\nY\u0131\u011f\u0131n (Stack) Veri Yap\u0131s\u0131: LIFO Prensibi ve Temel Operasyonlar\u0131 Nelerdir?<\/h3>\n
\n
true<\/code>, de\u011filse false<\/code> d\u00f6nd\u00fcr\u00fcr.<\/li>\nMonotonik Y\u0131\u011f\u0131n: S\u0131ral\u0131 Bir Y\u0131\u011f\u0131n Neden Algoritmalarda G\u00fc\u00e7l\u00fc Bir Ara\u00e7t\u0131r?<\/h3>\n
\n
O(N)<\/code> gibi do\u011frusal bir zaman karma\u015f\u0131kl\u0131\u011f\u0131 sa\u011flar; yani, dizinin boyutu ne kadar b\u00fcy\u00fck olursa olsun, \u00e7\u00f6z\u00fcm s\u00fcresi dizinin boyutuyla orant\u0131l\u0131 olarak artar. Kaba kuvvet \u00e7\u00f6z\u00fcm\u00fcn\u00fcn O(N^2)<\/code> karma\u015f\u0131kl\u0131\u011f\u0131na k\u0131yasla bu, \u00f6zellikle b\u00fcy\u00fck veri setleri i\u00e7in muazzam bir iyile\u015fmedir. Monotonik y\u0131\u011f\u0131nlar, sadece NGE I de\u011fil, ayn\u0131 zamanda “Largest Rectangle in Histogram” (Histogramdaki En B\u00fcy\u00fck Dikd\u00f6rtgen), “Stock Span Problem” (Hisse Senedi Kapsam Problemi) ve “Next Smaller Element” (Bir Sonraki K\u00fc\u00e7\u00fck Eleman) gibi bir\u00e7ok ba\u015fka problemde de etkili \u00e7\u00f6z\u00fcmler sunar. Bu g\u00fc\u00e7l\u00fc veri yap\u0131s\u0131n\u0131 kullanarak, karma\u015f\u0131k g\u00f6r\u00fcnen algoritmik zorluklar\u0131n \u00fcstesinden gelmek \u00e7ok daha kolay hale gelir.<\/p>\nNext Greater Element I Problemini Monotonik Y\u0131\u011f\u0131n ile Ad\u0131m Ad\u0131m Nas\u0131l \u00c7\u00f6zebiliriz?<\/h3>\n
nums2<\/code> dizisini tek bir ge\u00e7i\u015fte i\u015fleyerek her eleman i\u00e7in NGE’sini bulmak ve bu bilgiyi bir haritada (hash map veya dictionary) saklamak yatar. Ard\u0131ndan, nums1<\/code> dizisindeki elemanlar i\u00e7in bu haritay\u0131 kullanarak sonu\u00e7lar\u0131 elde ederiz.<\/p>\n\n
\n
y\u0131\u011f\u0131n<\/code> (stack) olu\u015fturun. Bu y\u0131\u011f\u0131n, azalan monotonik bir d\u00fczende elemanlar\u0131 tutacakt\u0131r. Yani, y\u0131\u011f\u0131n\u0131n en \u00fcst\u00fcndeki eleman her zaman y\u0131\u011f\u0131ndaki di\u011fer elemanlardan daha k\u00fc\u00e7\u00fck veya e\u015fit olacakt\u0131r.<\/li>\nsonu\u00e7 haritas\u0131<\/code> (result map veya dictionary) olu\u015fturun. Bu harita, nums2<\/code> dizisindeki her eleman i\u00e7in NGE’sini saklayacakt\u0131r. Anahtar (key) olarak eleman\u0131n kendisi, de\u011fer (value) olarak ise NGE’si tutulacakt\u0131r.<\/li>\n<\/ul>\n<\/li>\nnums2<\/code> Dizisini \u0130\u015fleme:<\/strong>\nnums2<\/code> dizisini ba\u015ftan sona (veya sondan ba\u015fa, bu da m\u00fcmk\u00fcnd\u00fcr ama genellikle ba\u015ftan sona daha sezgiseldir) her eleman i\u00e7in a\u015fa\u011f\u0131daki ad\u0131mlar\u0131 uygulay\u0131n:<\/p>\n\n
current_num<\/code>):<\/strong> Dizideki mevcut eleman\u0131 al\u0131n.<\/li>\nstack.peek()<\/code>) current_num<\/code>‘dan k\u00fc\u00e7\u00fck oldu\u011fu s\u00fcrece:\n\n
stack.pop()<\/code>).<\/li>\ncurrent_num<\/code>‘dur. Dolay\u0131s\u0131yla, sonu\u00e7_haritas\u0131[\u00e7\u0131kar\u0131lan_eleman] = current_num<\/code> \u015feklinde kaydedin.<\/li>\n<\/ul>\ncurrent_num<\/code>‘dan b\u00fcy\u00fck veya e\u015fit elemanlar kalana kadar veya bo\u015falana kadar bu i\u015flemi s\u00fcrd\u00fcr\u00fcr. B\u00f6ylece y\u0131\u011f\u0131n, azalan monotonik \u00f6zelli\u011fini korur.<\/p>\n<\/li>\ncurrent_num<\/code>‘\u0131 y\u0131\u011f\u0131na ekleyin (stack.push(current_num)<\/code>). Bu eleman, kendisinden sonraki daha b\u00fcy\u00fck bir eleman bulunana kadar y\u0131\u011f\u0131nda kalacakt\u0131r.<\/li>\n<\/ul>\n<\/li>\nnums2<\/code> dizisindeki t\u00fcm elemanlar i\u015flendikten sonra, y\u0131\u011f\u0131nda hala elemanlar kalm\u0131\u015f olabilir. Bu elemanlar\u0131n nums2<\/code> dizisinde kendilerinden sonra gelen herhangi bir b\u00fcy\u00fck eleman\u0131 yoktur. Dolay\u0131s\u0131yla:<\/p>\n\n
sonu\u00e7_haritas\u0131[\u00e7\u0131kar\u0131lan_eleman] = -1<\/code> olarak kaydedin.<\/li>\n<\/ul>\n<\/li>\nnums1<\/code> Dizisi \u0130\u00e7in Sonu\u00e7lar\u0131 Bulma:<\/strong>\nnums1<\/code> dizisini ba\u015ftan sona dola\u015f\u0131n. Her eleman i\u00e7in, sonu\u00e7_haritas\u0131<\/code>‘nda kar\u015f\u0131l\u0131k gelen NGE de\u011ferini bulun ve bu de\u011ferleri yeni bir sonu\u00e7 dizisine ekleyin.<\/p>\n\n
sonu\u00e7_dizisi[i] = sonu\u00e7_haritas\u0131[nums1[i]]<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\nnums2<\/code> dizisini tek bir ge\u00e7i\u015fte i\u015fler ve her eleman y\u0131\u011f\u0131na en fazla bir kez itilir ve en fazla bir kez \u00e7\u0131kar\u0131l\u0131r. Bu nedenle, algoritman\u0131n zaman karma\u015f\u0131kl\u0131\u011f\u0131 O(nums2.length + nums1.length)<\/code> veya k\u0131saca O(N)<\/code>‘dir (burada N, daha uzun olan dizinin boyutu). Kullan\u0131lan ekstra alan (y\u0131\u011f\u0131n ve harita) da O(N)<\/code>‘dir. Bu, kaba kuvvetin O(N^2)<\/code>‘sine g\u00f6re \u00f6nemli bir performans art\u0131\u015f\u0131d\u0131r.<\/p>\nUygulamal\u0131 \u00d6rnek ve Kod \u0130ncelemesi: Monotonik Y\u0131\u011f\u0131n NGE I \u0130\u00e7in Nas\u0131l Kullan\u0131l\u0131r?<\/h3>\n
\nnums1 = [4, 1, 2]<\/code>
\nnums2 = [1, 3, 4, 2]<\/code><\/p>\n\n
y\u0131\u011f\u0131n = []<\/code>, sonuc_haritasi = {}<\/code><\/li>\nnums2<\/code>‘yi \u0130\u015fleme:<\/strong>\n\n
num = 1<\/code>):<\/strong>\n\n
y\u0131\u011f\u0131n.push(1)<\/code> -> y\u0131\u011f\u0131n = [1]<\/code><\/li>\n<\/ul>\n<\/li>\nnum = 3<\/code>):<\/strong>\n\n
y\u0131\u011f\u0131n.pop()<\/code> (1 \u00e7\u0131kar) -> sonuc_haritasi[1] = 3<\/code>. y\u0131\u011f\u0131n = []<\/code><\/li>\ny\u0131\u011f\u0131n.push(3)<\/code> -> y\u0131\u011f\u0131n = [3]<\/code><\/li>\n<\/ul>\n<\/li>\nnum = 4<\/code>):<\/strong>\n\n
y\u0131\u011f\u0131n.pop()<\/code> (3 \u00e7\u0131kar) -> sonuc_haritasi[3] = 4<\/code>. y\u0131\u011f\u0131n = []<\/code><\/li>\ny\u0131\u011f\u0131n.push(4)<\/code> -> y\u0131\u011f\u0131n = [4]<\/code><\/li>\n<\/ul>\n<\/li>\nnum = 2<\/code>):<\/strong>\n\n
y\u0131\u011f\u0131n.push(2)<\/code> -> y\u0131\u011f\u0131n = [4, 2]<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ul>\n<\/li>\nnums2<\/code> \u0130\u015flemi Bitti:<\/strong>\n\n
sonuc_haritasi = {1: 3, 3: 4}<\/code><\/li>\n[4, 2]<\/code>. Bu elemanlar\u0131n nums2<\/code>‘de kendilerinden sonra b\u00fcy\u00fck eleman\u0131 yoktur.<\/li>\ny\u0131\u011f\u0131n.pop()<\/code> (2 \u00e7\u0131kar) -> sonuc_haritasi[2] = -1<\/code>. y\u0131\u011f\u0131n = [4]<\/code><\/li>\ny\u0131\u011f\u0131n.pop()<\/code> (4 \u00e7\u0131kar) -> sonuc_haritasi[4] = -1<\/code>. y\u0131\u011f\u0131n = []<\/code><\/li>\nsonuc_haritasi = {1: 3, 3: 4, 2: -1, 4: -1}<\/code><\/li>\n<\/ul>\n<\/li>\nnums1<\/code> \u0130\u00e7in Sonu\u00e7lar\u0131 Bulma:<\/strong>\n\n
nums1[0] = 4<\/code> -> sonuc_haritasi[4] = -1<\/code><\/li>\nnums1[1] = 1<\/code> -> sonuc_haritasi[1] = 3<\/code><\/li>\nnums1[2] = 2<\/code> -> sonuc_haritasi[2] = -1<\/code><\/li>\n<\/ul>\n<\/li>\n<\/ol>\n[-1, 3, -1]<\/code><\/p>\n\nclass Solution:\n def nextGreaterElement(self, nums1: list[int], nums2: list[int]) -> list[int]:\n stack = [] # Monotonik y\u0131\u011f\u0131n\n next_greater = {} # nums2'deki her eleman i\u00e7in NGE'sini saklayacak harita\n\n # nums2 dizisini dola\u015farak her eleman\u0131n NGE'sini bul\n for num in nums2:\n # Y\u0131\u011f\u0131n bo\u015f de\u011filse ve y\u0131\u011f\u0131n\u0131n tepesindeki eleman mevcut num'dan k\u00fc\u00e7\u00fckse\n # Bu, y\u0131\u011f\u0131ndaki tepedeki eleman\u0131n NGE'sinin mevcut num oldu\u011fu anlam\u0131na gelir\n while stack and stack[-1] < num:\n popped_element = stack.pop()\n next_greater[popped_element] = num\n # Mevcut num'\u0131 y\u0131\u011f\u0131na ekle (azalan monotonik d\u00fczeni koruyarak)\n stack.append(num)\n \n # nums2'deki t\u00fcm elemanlar i\u015flendikten sonra y\u0131\u011f\u0131nda kalan elemanlar\n # kendilerinden sonra b\u00fcy\u00fck bir eleman bulamam\u0131\u015f demektir. NGE'leri -1'dir.\n while stack:\n popped_element = stack.pop()\n next_greater[popped_element] = -1\n \n # nums1'deki elemanlar i\u00e7in NGE de\u011ferlerini bul ve sonu\u00e7 listesine ekle\n result = []\n for num in nums1:\n result.append(next_greater.get(num, -1)) # E\u011fer num haritada yoksa -1 d\u00f6nd\u00fcr\n \n return result\n\n# \u00d6rnek kullan\u0131m:\nsolver = Solution()\nnums1_example = [4, 1, 2]\nnums2_example = [1, 3, 4, 2]\noutput = solver.nextGreaterElement(nums1_example, nums2_example)\nprint(f\"Nums1: {nums1_example}\")\nprint(f\"Nums2: {nums2_example}\")\nprint(f\"Next Greater Elements: {output}\") # \u00c7\u0131kt\u0131: [-1, 3, -1]\n\nnums1_example_2 = [2,4]\nnums2_example_2 = [1,2,3,4]\noutput_2 = solver.nextGreaterElement(nums1_example_2, nums2_example_2)\nprint(f\"Nums1: {nums1_example_2}\")\nprint(f\"Nums2: {nums2_example_2}\")\nprint(f\"Next Greater Elements: {output_2}\") # \u00c7\u0131kt\u0131: [3, -1]\n<\/code><\/pre>\n<\/div>\nstack<\/code> listesi Python'da bir y\u0131\u011f\u0131n gibi davran\u0131r (append<\/code> ile push, pop<\/code> ile pop, [-1]<\/code> ile peek). next_greater<\/code> s\u00f6zl\u00fc\u011f\u00fc (dictionary), her eleman i\u00e7in NGE'sini saklar. Kodun ak\u0131\u015f\u0131, nums2<\/code> dizisini tarayarak next_greater<\/code> haritas\u0131n\u0131 doldurur ve ard\u0131ndan nums1<\/code>'deki elemanlar i\u00e7in bu haritadan sonu\u00e7lar\u0131 \u00e7eker. Bu yap\u0131, hem anla\u015f\u0131l\u0131r hem de olduk\u00e7a verimli bir \u00e7\u00f6z\u00fcm sunar.<\/p>\nGer\u00e7ek D\u00fcnya Senaryolar\u0131: Monotonik Y\u0131\u011f\u0131n\u0131n \u0130\u015f Hayat\u0131ndaki Pratik Uygulamalar\u0131 Nelerdir?<\/h3>\n
\n
O(N)<\/code> zamanda \u00e7\u00f6z\u00fclebilir. Y\u0131\u011f\u0131n, d\u00fc\u015f\u00fc\u015f trendindeki fiyatlar\u0131 takip eder ve yeni bir y\u00fckseli\u015f geldi\u011finde, \u00f6nceki d\u00fc\u015f\u00fc\u015fleri ne kadar s\u00fcreyle geride b\u0131rakt\u0131\u011f\u0131n\u0131 h\u0131zl\u0131ca hesaplar. \u00d6rne\u011fin, belirli bir hisse senedinin fiyat\u0131 bug\u00fcn 100 TL ise, monotonik y\u0131\u011f\u0131n sayesinde son 5 i\u015flem g\u00fcn\u00fcnde 100 TL'den daha d\u00fc\u015f\u00fck seyretti\u011fini an\u0131nda bulabiliriz.<\/p>\n<\/li>\nO(N)<\/code> zamanda \u00e7\u00f6zer. B\u00f6ylece, karma\u015f\u0131k g\u00f6r\u00fcnt\u00fc analizleri \u00e7ok daha h\u0131zl\u0131 ger\u00e7ekle\u015ftirilebilir.<\/p>\n<\/li>\nSonu\u00e7: Monotonik Y\u0131\u011f\u0131n ile Algoritmik Problemlere Hakim Olmak<\/h3>\n
O(N)<\/code> gibi do\u011frusal bir zaman karma\u015f\u0131kl\u0131\u011f\u0131na nas\u0131l ula\u015ft\u0131\u011f\u0131m\u0131z\u0131 net bir \u015fekilde anlad\u0131k. Bu verimlilik, \u00f6zellikle b\u00fcy\u00fck veri setleriyle \u00e7al\u0131\u015f\u0131rken kritik \u00f6neme sahiptir. Dahas\u0131, monotonik y\u0131\u011f\u0131n\u0131n sadece NGE I ile s\u0131n\u0131rl\u0131 kalmay\u0131p, finansal analizlerden g\u00f6r\u00fcnt\u00fc i\u015flemeye, veri analizinden IoT uygulamalar\u0131na kadar bir\u00e7ok ger\u00e7ek d\u00fcnya senaryosunda nas\u0131l pratik \u00e7\u00f6z\u00fcmler sundu\u011funu ke\u015ffettik. Bu uygulamalar, bu veri yap\u0131s\u0131n\u0131n sadece teorik bir kavram olmaktan \u00f6te, i\u015f d\u00fcnyas\u0131nda somut faydalar sa\u011flayan bir ara\u00e7 oldu\u011funu g\u00f6stermektedir.<\/p>\nS\u0131k\u00e7a Sorulan Sorular (SSS)<\/h3>\n
nums1<\/code> ve nums2<\/code>) aras\u0131nda, nums1<\/code>'deki elemanlar\u0131n nums2<\/code>'deki kar\u015f\u0131l\u0131klar\u0131 i\u00e7in sonraki b\u00fcy\u00fck eleman\u0131 bulmaya odaklan\u0131r. NGE II ise genellikle tek bir dizi \u00fczerinde \u00e7al\u0131\u015f\u0131r ve dizinin dairesel (circular) oldu\u011funu varsayar. Yani, dizinin son eleman\u0131ndan sonra ilk eleman gelir ve arama bu \u015fekilde devam eder. Bu da \u00e7\u00f6z\u00fcmde k\u00fc\u00e7\u00fck de\u011fi\u015fiklikler gerektirir.<\/p>\nO(N^2)<\/code>), monotonik y\u0131\u011f\u0131n her eleman\u0131 y\u0131\u011f\u0131na en fazla bir kez ekler ve en fazla bir kez \u00e7\u0131kar\u0131r (O(N)<\/code>). Bu tek ge\u00e7i\u015fli i\u015flem, zaman karma\u015f\u0131kl\u0131\u011f\u0131n\u0131 \u00f6nemli \u00f6l\u00e7\u00fcde d\u00fc\u015f\u00fcr\u00fcr.<\/p>\n