Monotonic Stack

I will cover all the LeetCode Patterns for coding Interviews mentioned by a few folks. I'll write the code using C#. Today's post is related to ?????????????????? ??????????. If anyone sees any area of improvement please feel free to add.

?????????????????? ?????????? maintaining elements in either increasing or decreasing order. It is commonly used to efficiently solve problems such as finding the next greater or smaller element in an array etc

Find the next greater element in an array.

• Initialize an empty stack.
• Iterate through the elements and for each element
• while stack is not empty AND top of stack is less than the current element pop element from the stack. Push the current element onto the stack.
• At the end of the iteration, the stack will contain the monotonic decreasing order of elements.

using System;

using System.Collections.Generic;

using System.Linq;

using System.Text;

using System.Threading.Tasks;

namespace LeetCodePattren

{

internal class MonotonicStack

{

public int[] nextGreaterElement(int[] arr)

{

// result array to store the final result

int[] result = new int[arr.Length];

// stack to check and store the next value

Stack<int> stack = new Stack<int>();

for (int i = 0; i < result.Length; i++)

{

result[i] = -1;

}

for (int i = 0; i < arr.Length; i++)

{

while (stack.Count > 0 && arr[stack.Peek()] < arr[i])

{

result[stack.Peek()] = arr[i];

stack.Pop();

}

// decreasing stack

stack.Push(i);

}

for (int i = 0; i < result.Length; i++)

{

Console.WriteLine(result[i]);

}

return result;

}

public static void Main(string[] args)

{

int[] arr = { 6, 4, 9, 5, 3, 1, 8, 2 };

MonotonicStack monotonicStack = new MonotonicStack();

monotonicStack.nextGreaterElement(arr);

Console.ReadLine();

}

}

}