C# || MinStack – How To Implement Minimum Element Stack Using C#
The following is a module with functions which demonstrates how to implement minimum element stack using C#.
1. MinStack – Problem Statement
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack class:
- MinStack() initializes the stack object.
- void push(int val) pushes the element val onto the stack.
- void pop() removes the element on the top of the stack.
- int top() gets the top element of the stack.
- int getMin() retrieves the minimum element in the stack.
Example 1:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]Output
[null,null,null,null,-3,null,0,-2]Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
2. MinStack – Solution
The following is a solution which demonstrates how to implement minimum element stack.
The main idea of this solution is to have a way to keep track of the minimum value every time an item is pushed onto the stack.
When a new value is pushed onto the stack, it is checked against the last minimum to see if the current value is a minimum. Every time a new item is added, we keep track of the minimum value for each push.
In this solution:
- When the Top function is called, the current top value is returned
- When the GetMin function is called, the minimum value at the time the top value was pushed onto the stack is returned
- When the Push function is called, the value and the current minimum value is pushed onto the stack
A list< pair < int, int>> is used to keep track of the current item pushed onto the stack, and the minimum value at the time the item was pushed onto the stack.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
// ============================================================================ // Author: Kenneth Perkins // Date: Oct 24, 2021 // Taken From: http://programmingnotes.org/ // File: Solution.cs // Description: Demonstrates how to implement minimum element stack // ============================================================================ public class MinStack { private List<KeyValuePair<int, int>> data; /** initialize your data structure here. */ public MinStack() { // Initialize the list // The pair key is the stack value // The pair value is the current stack minimum value data = new List<KeyValuePair<int, int>>(); } public void Push(int val) { // Determine minimum value. // If the stack is not empty, compare against the last min value var currentMinValue = val; if (data.Count > 0) { currentMinValue = Math.Min(currentMinValue, GetMin()); } // Add new entry to the stack, saving the value and current minimum data.Add(new KeyValuePair<int, int>(val, currentMinValue)); } public void Pop() { data.RemoveAt(data.Count - 1); } public int Top() { // Return the current top value return data[data.Count - 1].Key; } public int GetMin() { // Return the current minimum value return data[data.Count - 1].Value; } }// http://programmingnotes.org/ |
QUICK NOTES:
The highlighted lines are sections of interest to look out for.
The code is heavily commented, so no further insight is necessary. If you have any questions, feel free to leave a comment below.
Once compiled, you should get this as your output for the example cases:
[null,null,null,null,-3,null,0,-2]
Leave a Reply