什麼是單調棧

單調棧是一種特殊的棧結構，它維護了棧內元素的一種單調性，即要麼是單調遞增（棧底到棧頂），要麼是單調遞減（棧底到棧頂）。

單調棧的主要用途是找到數組中某個元素的下一個更大（或更小）的元素，這種結構在處理數組問題時非常有用，可以將某些算法的時間複雜度從O(n²)最佳化到O(n)。單調棧的實現方式是在遍歷數組時，對於每個元素，如果它比棧頂元素小（對於單調遞增棧）或大（對於單調遞減棧），則將棧頂元素出棧，直到找到一個比該元素小（對於單調遞增）或大（對於單調遞減）的元素，然後將該元素入棧。